二分探索の練習平均最小化小数の闇に注意割と平均最大（小）化好きかもしれない。 #include <bits/stdc++.h> using namespace std; struct edge{ int from; double time; int ren; }; const int INF = 1000000000; int n,m,c; double dp[10009]; bool flag[10006]; vector<edge> g</edge></bits/stdc++.h>…

貪欲法 計算量がO(NM)でNM = 10^7だから「計算量ちょっとやばいかなー」と思ってできるだけ高速に実行できるように頑張ったけど実際そんなことやる必要なかった問題。 #include <bits/stdc++.h> using namespace std; int n,m,co,ans,yaruki[10003],ruisekiyaruki[10003],oy</bits/stdc++.h>…

難しかったけど解ける気がしたのでめっちゃがんばって無理やり解いた。WAとRE大量発生しまくってとてもつらい思いをした。生のソースはっつけます。解法とか書く気力がおきない。 #include <bits/stdc++.h> using namespace std; const int INF = 1000000000; int n,c; int </bits/stdc++.h>…

以前バケット法でも解けますとか言ってたので解いた。第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack History 第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack Historyバケ…

解法：トポロジカルソート過去の自分のほうが頭いい気がする。↓ 第7回日本情報オリンピック 春合宿 1日目 「色紙」 - intさわだんのBlack History 第7回日本情報オリンピック 春合宿 1日目 「色紙」 - intさわだんのBlack History #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

なんか前解いたことある気がする。解法：DPコーナーケースがある。 #include <bits/stdc++.h> using namespace std; const int INF = 100000000; int n,ans=-INF,sa[100004][2],am=-INF,dp[100003]; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++)scanf("%d%d",&sa</bits/stdc++.h>…

二次元累積和やるだけです。ある区間に何個-1があるかを二次元累積和で求められるようにし。 その区間の資源の合計も二次元累積和で求められるようにする。 DPでの解法もある（？） 計算量はO(n ^ 2).累積和についてよくわからなかったら、 もし女子大生プロ…

このブログを参考にしました。[JOI合宿]2007-Day1:Factorial：Snowing day：So-net blog [JOI合宿]2007-Day1:Factorial：Snowing day：So-net blog #include <bits/stdc++.h> using namespace std; int ans; int main(){ int n; scanf("%d",&n); for(int i = 2;i <=n;i+=2){</bits/stdc++.h>…

priority_queueやsortを使い、大きいほうから順に並べてその得点の順位を決めます。計算量はO(n log n)だけどこの問題はそこまで計算量気にしなくてよさそう。 #include <bits/stdc++.h> using namespace std; int d[100005]; int jun[120]; int main(){ priority_queue<int> que</int></bits/stdc++.h>…

バケット法を使うという解法もあるけど実は使わなくても可能という問題。探索＆再帰＆枝刈り #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; int n,m,d,k; bool used[100002]; int ch[1002][1002]; int z[100002][2]; vector<int> e[100002]; int ans = 0; int </int></int,int></bits/stdc++.h>…

トポロジカルソートやるだけ。 JOI本選過去問の「最悪の記者」に類似している。→リンク bool used[1002];//使ったかどうか int n,w,h; int s[1002][4];//0,1:左上、2,3:右下 int ans[1002];//答え逆順 int m[102][102];//map int inn[4] = {100,100,0,0}; in…

mapを使うことが出きるかを問うている問題。 実はa,b,の値は必要ない。 テストケース9が謎に最強だった。 typedef pair<int,int> P; int main(){ int n,a,b; scanf("%d%d%d",&n,&a,&b); map<P,int> m; int ans1=0,ans2=0; for(int g = 0;g < n;g++){ int p,q,r,s; scanf("%d%</p,int></int,int>…

問題文を読んで3秒で二分探索だと悟った。 こういう解法の決めつけはよくないと思うけど顕著すぎるんじゃ～ int n,m; int x[100003]; int y[100003]; bool ch(int d){ int co = 0; int h = x[0] + d; co++; for(int i = 1;i < m;i++){ if(x[i] > h){ co++; h…

典型DP 予選で出てもおかしくないレベルなので解説は割愛。#include や、using namespace std;は省略することにしました。 const int INF = 1000000000; int n,d; int dp[400][3002][3]; int p[400][3002]; int main(){ scanf("%d%d",&n,&d); for(int i = 0;…

木の深いところから順に見ていく。すべての人のやる気が負の時のコーナーケースに注意計算量O(N). int n; int d[100003][2]; int ans[100003]; int ho=0; int main(){ scanf("%d",&n); ho = 0; int m = -100000000; for(int i = 1;i <= n;i++){ scanf("%d%d"…