詳しくは蟻本p99参照クラスカルやるだけ。unionfindとkruskalなんも見ないで実装できたのでgood. #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 20003; const int MAX_E = 50003; int par[MAX_N]; int rank[MAX_N]; struct edge{int from,to,</algorithm></cstdio>…

半分全列挙するだけ。一発ACだった。 #include <cstdio> #include <algorithm> using namespace std; int a[4003],b[4003],c[4003],d[4003]; int e[16000005]; int n; int main(){ scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); } for</algorithm></cstdio>…

蟻本にある問題。蟻本頭良すぎて焦る。しゃくとり法。 #include <cstdio> #include <algorithm> #include <map> #include <set> using namespace std; int main(){ int p,a[1000003]; scanf("%d",&p); for(int i = 0;i < p;i++) scanf("%d",&a[i]); set<int> all; for(int i = 0;i < p;i++){ al</int></set></map></algorithm></cstdio>…

二分探索・平均最大化。 日本TLE怖い協会 もうこの問題は解きたくない。 #include <cstdio> #include <algorithm> #include <functional> #include <utility> using namespace std; int n,k; int v[100010]; int w[100010]; pair<double, int> p[100012]; bool ans(double x){ for(int i = 0;i < n;i++){ p[i] = ma</double,></utility></functional></algorithm></cstdio>…

普通に平均最大化をする。小数の闇を見た。 #include <cstdio> #include <algorithm> #include <functional> #include <iostream> #include <math.h> using namespace std; int n,k,d[1002][2]; double t[1002]; bool ch(double x){ for(int i = 0;i < n;i++){ t[i] = 100.00 * d[i][0] - x * d[i][1]; } sort(</math.h></iostream></functional></algorithm></cstdio>…

普通に二分探索使わなくてもいいのでは？とおもって調べてみたら普通に貪欲法でいけるらしいです。下のブログを参考にしました。POJ-3045 : Cow Acrobats - komiyamの日記 POJ-3045 : Cow Acrobats - komiyamの日記 #include <cstdio> #include <algorithm> #include <utility> using nam</utility></algorithm></cstdio>…

もう解きたくない・ 黒歴史ソース #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000002; int n,k,d[100003]; bool ch( long long int x){ long long int u = 0; for(int i = 0;i < n;i++){ if(d[i] > x){ u += (d[i] - x + k -2)/(k-1); }</algorithm></cstdio>…

二分探索で最小値を求める。 #include <cstdio> using namespace std; const int INF = 100002; int n,m,d[1000002]; bool ch(int x){ int u = 1; int sum = 0; for(int i = 0;i < n;i++){ if(d[i] > x)return false; if(d[i] + sum > x){ u++; sum = d[i]; }else{ s</cstdio>…

顕著な二分探索。説明不要な気がする。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int l,n,m,d[50001]={0}; bool ch(int x){ int u = 0; int pre = 0; for(int i = 1;i <= n+1;i++){ if(d[pre] + x > d[i]){ u++; }else{ pre =</algorithm></cstdio>…

蟻本にある。 二分探索使わなくても解けるのだろうか。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int n,c,p[100001]; bool ch(int x){ int nau = 0,sum = 1,pre = p[nau]; while(nau < n && sum < c){ if(pre + x <= p[nau]){</algorithm></cstdio>…

解法：プリム法、またはクラスカル法をやるだけ。なぜプリム法を選んだのかは自分でもわからん。気づいたら組んでいた。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; const int MAX_V = 100; const int INF = 100000000; int cost[MAX_V][MAX_V]; i</iostream></algorithm></cstdio>…

ベルマンフォード法で負閉路の検出をするだけ。細かいところは問題文参照してください。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int MAX_E = 6000; const int MAX_V = 600; const int INF = 100000000; struct edge { int from,to,cost;</string.h></algorithm></cstdio>…

エラトステネスの篩、生半可な知識で適当に実装してみたら一発で通ったのでらっきー。bool型の配列って全部初期化すること可能なんでしょうか。 #include <cstdio> #include <iostream> using namespace std; int main(){ int n; while(cin >> n){ bool d[1000000]; int ans = </iostream></cstdio>…

union find参考にさせていただきました。 http://d.hatena.ne.jp/sndr/20121221/1356071878 #include <cstdio> #include <iostream> using namespace std; int par[200003];//親 int rank[200003];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i]</iostream></cstdio>…

顕著なunion-find実行速度遅すぎる。 #include <cstdio> #include <iostream> using namespace std; int par[1002];//親 int rank[1002];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }</iostream></cstdio>…

解法：最長増加部分列(LIS)蟻ゲーです。 #include <cstdio> #include <algorithm> const int INF = 100000000; using namespace std; int main(){ int n; scanf("%d",&n); while(n--){ int p; int d[40003]={0}; int dp[40003] = {0}; scanf("%d",&p); for(int i = 0;i < p;i++)</algorithm></cstdio>…

闇。このブログを参考にさせていただきました。 http://d.hatena.ne.jp/atetubou/20110528/1306544909 以上。 #include <cstdio> #include <algorithm> #include <utility> using namespace std; int main(){ int t; scanf("%d",&t); while(t--){ int n; bool use[5003]; int ans = 0; pa</utility></algorithm></cstdio>…

蟻ゲー以上。 #include <cstdio> #include <string.h> using namespace std; int dp[100003]; int main(){ while(1){ int n,m; int d[102][2]; scanf("%d%d",&n,&m); if(n == 0)break; for(int i = 0;i < n;i++){ scanf("%d",&d[i][0]); } for(int i = 0;i < n;i++){ scanf("%d</string.h></cstdio>…

N年ぶりにDPの問題を解いたけどなんとかできた。。。解法：DP dp[i] = max(dp[i-1],終わる時間がiの中で最も大きいもの);実際問題から計算量O(N)しかありえないっぽいし解法しぼれたのでよかった。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P</int,int></algorithm></cstdio>…

問題文解法：DP中のDP(?) #include <cstdio> #include <algorithm> using namespace std; int main(){ int t,w,dp[3002][32] = {0}; bool ch[1003]; scanf("%d%d",&t,&w); for(int i = 0;i < t;i++){ int tmp; scanf("%d",&tmp); if(tmp == 1){ ch[i+1] = true; }else{ ch[i+1] </algorithm></cstdio>…

なぞに顕著な貪欲。 大きいほうから順に消していけばよい。 #include <cstdio> #include <algorithm> #include <cmath> #include <functional> #include <iostream> using namespace std; int main(){ int n; double d[103] = {0}; scanf("%d",&n); for(int i = 0;i < n;i++){ cin >> d[i]; } sort(d, d + n ,</iostream></functional></cmath></algorithm></cstdio>…

解法：貪欲 こめんと：priority_queueはとても便利。 #include <cstdio> #include <utility> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; typedef pair<int,P> PP; int main(){ int out[50002]={0}; int n; int ans = 0; priority_queue<PP ,vector<PP>,greater<PP> > que; scanf("%d",&n</pp></pp></int,p></int,int></vector></queue></utility></cstdio>…

こういう問題苦手。わかりやすいコーナーケースに気づけなくてめちゃくちゃ時間がかかった。解法：貪欲法。 #include <cstdio> #include <algorithm> #include <utility> #include <cmath> using namespace std; int cas = 1; int main(){ while(1){ pair<int,int> is[1003]; int n,d,ans= 1; scanf("%d%d</int,int></cmath></utility></algorithm></cstdio>…

解法：全探索(dfs)やるだけである。思ったより簡単で腰を抜かす。 #include <set> #include <iostream> #include <cstdio> using namespace std; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; set<int> tmp; int ans = 0; int d[6][6]; void dfs(int x,int y,int s,int g){ if(s == 6)</int></cstdio></iostream></set>…

全列挙。next_permutationを使うとらく。やるだけです。ちょっと数学力が足りないのでせこい技を使ってしまった。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ int n,sum; int d[12]; int c[12][12] = {0}; c[0][0] = 1; c[1][0] = 1; </iostream></algorithm></cstdio>…

ちなみに問題はこちらです。 ぱっと見面倒くさそうだなぁと思ったけどそうでもなかった。 mapは便利。解法：幅優先探索 "01234567"から0を移動させた回数の最小を全部求めてバッと答えだす。（日本語苦手 #include <map> #include <string> #include <queue> #include <utility> #include <iostream></iostream></utility></queue></string></map>…

int par[MAX_N]; //親 int rank[MAX_N]; //木の深さ //n要素で初期化 void init(int n) { for(int i = 0;i < n;i++){ par[i] = i; rank[i] = 0; } } //木の根を求める int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } …

#include <cstdio> #include <algorithm> #include <queue> #include <vector> const int INF = 10000; using namespace std; // struct edge { int to ,cost; }; struct edge { int to, cost; edge(int _to, int _cost) {to = _to; cost=_cost;} }; typedef pair<int ,int>P; int V; vector<edge> G[8]; int d[</edge></int></vector></queue></algorithm></cstdio>…

完全にメモです。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int dp[8][8] = {0}; int V; const int INF = 10000; void wf(){ for(int k = 0;k < V;k++){ for(int i = 0;i < V;i++){ for(int j = 0;j < V;j++) dp[i][j] = min(dp[i][j],dp[i][k] </iostream></algorithm></cstdio>…