2014-09-01から1ヶ月間の記事一覧
明日から10月はいるんで真面目に頑張りますね。後悔したくないんで。はい。
進捗ダメですが(プログラミング関連が)楽しすぎてやばいです。
10月からは頑張ります
解法:プリム法、またはクラスカル法をやるだけ。なぜプリム法を選んだのかは自分でもわからん。気づいたら組んでいた。 #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>…
なんか進捗わるすぎてメンヘラ(仮)になってきたが簡単な問題だけでも解く 結局こういうときに頑張れるかor notで今後大きく変わってくるんだと思う。 #include <cstdio> #include <iostream> using namespace std; int gcd( int m, int n ) { if ( ( 0 == m ) || ( 0 == n ) </iostream></cstdio>…
英語全く読めないから、AOJの問題だ、やったー とか思ってたら問題文英語だったので死
久々にAOJにアクセス
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>…