GCJ Round1A-Cを振り返っておく
Round1落ちしてしまった…全体を振り返るに，しょんぼりなミスがいつも以上に多かったと思う．
やはりあの呪いか．
ミスを繰り返さないように，メモっておこう．
Round1A
なんかGCJがお祭りな感じだなーとか思いながら，今回通れないと次回でるの大変だなーとか思いながら参加．
A. Rotates
やるだけ，なんだけど，回転と幅詰めに手間取った．
前も手間取って，意外とでるからライブラリ入りしとこうかな．特にミスなし．
B. Make it Smooth
DPなのはすぐにわかるけど，上手く考えられない．small通そうとしたけど，なんか場合分けができない．
場合分けじゃなくて再帰全探索が良かった．これにこだわったのがこのラウンドの１番の失敗．
C. Number Game
本番中ろくに読まなかった．イクナイ．読んでみたら，smallはmapとかでキャッシュつければ通りそうってことはわかった．
結果
Aのみで1000ちょっと．全体としては戦略的ミスだった．一回目だしいいかっていう油断もあった．
でも全部とけなきゃ．
Round1B
一日二回か．しんどい．って思いながら参加．本番前に呪いのキーワードを吐いてしまった．これが転落の始まりだったのだろうか．
A. File Fix-It
やるだけ．日本人最速だったらしい．っていうのを聞いて，考え方が守りに入った．small通せばいっかなって．
B. Picking Up Chicks
とりあえずsmallを通そうとして，queueでも使ってswap全部試そうと思った．が，答え合わない…
本番後検証したら，queue中のbreakに何故かswapがK回超えたらやめるになってた．Kは最低限の鶏の数だよ…
ひどい凡ミス
途中皆結構点数あげてて，これはlarge通さないと勝てないと思って方針を変えた(たぶん遅かったけど)．
冷静に考えると，largeも貪欲にやっていけばいけそうってすぐ気づいた．けど，なんでか通らない．
本番後に少し条件が抜けてたことが発覚．2,3行足りなかった．
C. Your Rank is Pure
読めない！ていうか素数の話なに？？
本番後に説明聞いたら，とりあえずDPはすぐわかって，理解できたらとけてたかなーと思う．
ググル様は英語できない人に用ないんだなぁ．
結果
1700ぐらい．Bを冷静に通したかった．もしくは読みたかった．
Round1B
A. Rope Intranet
やるだけ．簡単すぎてなんども確認して1分ほどロスした．
B. Load Testing
読めないんですよ．まだ読めてない．皆結構解いてたので，簡単なんだろうなーと思って1時間以上読んだけどよくわからなかった．ゲシュタルト崩壊した．
数字の大きさから，なんとなーくBinary SearchでLargeをとくのかなーって思った．そうだったらしい．読めない．
[追記]バイナリサーチと言うかアドホック．意味を教えてもらって，最初トップダウンに考えていてイミフだったけど，ボトムアップに考えたらすぐわかった．でも，説明を日本語で聞いてもなかなか理解できなかったから本番中は無理ぽ．
C. Making Chess Boards
Bが読めないので，とりあえずCに来た．Cを読んだらLargeは知らないけどsmallはやるだけっぽかったのでガリガリ書き始める．
30分程でだいたいかけて，40分ぐらいで提出．small合わない…
本番後に少し条件が抜けていたことがわかった．数行訂正すれば直ってた．気づきにくいといえば気づきにくい．
結果
1300ぐらい．英語が読めなかったことと，Cでミスに気づかなかったのが原因かな．
でもCをn^5で出してたかというと怪しい．その根性はなかったなァ…通るなんて．
謎
PKU 2671なんだけど，while (1);を書くかどうかでACがWAになる．
ダイクストラで解いたのだけど，擬似コードはこんな感じ．
int bfs(){ while (!q.empty()){ } while (1); // これを消すとWA } int main(){ ... ... cout << bfs() << endl; }
なんぞこれ？
実際のコード
#include <iostream> #include <queue> #include <cstdio> using namespace std; int distsum[300][300]; int costsum[300][300]; int dist[300]; int cost[300]; int totaldist,totalcost; int dp[300][300][2]; int N; #define RIGHT 1 #define LEFT 0 struct State{ int left,right,which; int cost; bool operator<(const State& s)const{ return cost > s.cost; } }; int bfs(){ priority_queue<State> up; up.push((State){0,0,0,0}); up.push((State){0,0,1,0}); while (!up.empty()){ State st = up.top(); up.pop(); int l = st.left; int r = st.right; int c = st.cost; int w = st.which; //cout << l << " " << r << " " << c << " " << w << endl; if (c > dp[l][r][w]) continue; if ((r+1)%N==l) return c; int nl = (l + N - 1) % N; int nr = (r + 1) % N; int nc,nw; if (w == RIGHT){ nc = c + (totalcost - costsum[l][r])*distsum[nl][r]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[r][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } }else{ // from LEFT nc = c + (totalcost - costsum[l][r])*distsum[nl][l]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[l][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } } } while (1); // これを消すとWA } int main(){ while (1){ scanf("%d",&N); if (!N) break; totaldist = 0; totalcost = 0; for (int i=0;i<N;i++){ scanf("%d%d",&cost[i],&dist[i]); totalcost += cost[i]; totaldist += dist[i]; } for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<2;k++) dp[i][j][k] = 1 << 30; for (int i=0;i<N;i++){ int dsum=0,csum=0; for (int j=i;;j++){ j %= N; csum += cost[j]; costsum[i][j] = csum; distsum[i][j] = dsum; dsum += dist[j]; if ((j+1)%N==i) break; } } cout << bfs() << endl; } }
なんぞこれ？
追記
intの関数が値を返した方がいいというのはまさにそのとおりでございます．
でもwhile(1)
SRM469
すごい久しぶりに更新．５月病．
なんかやらなきゃいけないことをやってない気がして……
250 TheMoviesLevelOneDivOne
long long を掛け算につけなかった＼(^o^)／
500 TheMoviesLevelTwoDivOne
N=20の時点で1 << 20を考えて，TSPっぽいなーって思った．
とりあえず深さ優先で解いて，それにキャッシュをつけようとしたけど
なんだかバグが抜けなくて落ちるの確定だけど出してしまった．
僕の点数をだれかが喜んでいるはず……！！
そんなに難しくないと思うんだけどなァ．
プラクティスでといたけど，キャッシュを上手く使ってなくて一度TLEになった．
結果
1204ｗDiv2転落リーチ．次回からdiv2に上がりたい(ryになるかも．
最近やるきがでなくてサボっているのが良くない．人生に対して凡ミスをしている気がする．
Emacs23 on Windows のフォント設定
Windowsのemacs23.1で好きなフォントにする方法．調べたら EmacsWikiに書いてあったので，日本語で説明．
- emacsを起動してスクラッチバッファを開く．( C-x b *scratch* )
- (w32-select-font)と入力して，行末(')'の右)でC-j
- フォントを選択する窓が開くので，使いたいフォントを選んでOK
- バッファに次のようにフォント名が挿入される
(w32-select-font)
#("ＭＳ Ｐ明朝-12" 0 9 (charset cp932-2-byte))
- .emacsを開いて次のように入力する．ダブルクォーテーション内は(w32-select-font)で取得したフォントを指定する．
(set-face-font 'default "ＭＳ Ｐ明朝-12")
- emacsを再起動する
3140 Contestants Division
この問題は読むのが難しかった＞＜
the organizing committee can only afford to set the system up such that there will be only one way to transfer information from one university to another without passing the same university twice
この一文はグラフが木であることを意味しているらしい．
without passing the same university twiceの部分は，行ったり来たりしないでってこと，
only one way はpassが一通りしかないよってこと．
点から点の移動に，同じ点を二回通らないパスが一通りしかないことは木の必要十分条件ということだ．
で，この問題は，重みのある木の辺を，どこできると二つの木は近い重さになるかって問題で，まあ再帰とかでとけばいいと思います．
さくっと読める上海の方がすごいお(´・ω・`)
Codeforces Beta Round #9
凡ミスタグを付けなくてすむその日まで頑張る.
A Die Roll
(^p^)
B Running Student
sqrtの中身にintの範囲を超えるものを渡してて,それに気付かなかった(^p^)前にもsqrtの中身が負でバグってたことがあった。はぁ…
引数がおかしくなるケースがあるか考えよう
あとintの範囲は2^31^1 == 2147483647 だいたい 2 * 10^9.今回は(10^5)^2でint超えてた
D How many trees?
ノード数N,高さがH以上の2分木は何通り構成できる？
- 木の性質かなぁ…ググル
- 大した情報ないので考える.
- あるノードの左,右につけるものを考えるとき,自分より大きい数字がいくつ,小さい数字がいくつって情報だけでいいよな
- じゃあこれに今の高さの情報を付け加えて再帰かな
- 高さがH以上になるには,あるノードの左の木が高さH以上じゃなくても右の木がH以上ならいいから…
- 返り値に最大の高さと構成数が必要？pair？？
- って考えててこんがらかって終了
- 無条件の構成方法から,高さがH未満の構成方法を引くって方針に切り替えたらすんなり書けた
#include <iostream> #include <cstdio> #include <cctype> #include <cstring> #include <map> #include <queue> #include <algorithm> #include <complex> #include <set> #include <vector> #include <bitset> #define REP(i,N)for(int i=0;i<(int)N;i++) #define MP(a,b) make_pair(a,b) using namespace std; int nextInt(){ int ret=0,sign=1; char c=' '; while (!isdigit(c=getchar())){ if (c==EOF) return -1; if (c=='-') sign=-1; } do{ ret=ret*10+(c-'0'); }while (isdigit(c=getchar())); return ret*sign; } void printlineInt(int num){ char str[101]; if (num<0) num=-num,putchar('-'); else if (num==0) {puts("0");return;} str[100]='\0'; int i=99; for (;num;i--){ str[i]=num%10+'0'; num/=10; } puts(&str[i+1]); return; } //template end int N,H; long long dp[36][36][36]; long long dp2[36][36][36]; long long rec(int l,int u,int h){ if (dp[l][u][h] != -1LL) return dp[l][u][h]; //cout << h << " " << H << endl; if (h >= H) return dp[l][u][h] = 0; if (l == 0 && u == 0){ return dp[l][u][h] = 1LL; } long long r1=0,r2=0; REP(i,l){ r1 += rec(i,l-i-1,h+1); } if (!l) r1 = 1; REP(i,u){ r2 += rec(i,u-i-1,h+1); } if (!u) r2 = 1; //cout << l << " " << u << " " << h << " " << r1 * r2 << endl; return dp[l][u][h] = r1 * r2; } long long rec2(int l,int u,int h){ if (dp2[l][u][h] != -1LL) return dp2[l][u][h]; if (l == 0 && u == 0){ return dp2[l][u][h] = 1LL; } long long r1=0,r2=0; REP(i,l){ r1 += rec2(i,l-i-1,h+1); } if (!l) r1 = 1; REP(i,u){ r2 += rec2(i,u-i-1,h+1); } if (!u) r2 = 1; //cout << l << " " << u << " " << h << " " << r1 * r2 << endl; return dp2[l][u][h] = r1 * r2; } int main(){ N=nextInt(),H=nextInt(); REP(i,36) REP(j,36) REP(k,36) dp[i][j][k] = -1LL; REP(i,36) REP(j,36) REP(k,36) dp2[i][j][k] = -1LL; long long ans=0; REP(i,N){ ans += rec2(i,N-i-1,1) - rec(i,N-i-1,1); } cout << ans << endl; }
(^p^)
Codeforces Beta Round #8
Codeforces初参戦．WARush!!
A Train and Peter
簡単な問題なんだけど，最後まで自分の間違いに気付かなかった．終了後に手元でサンプルケースを作ってみたら一瞬で間違いがわかった…
教訓：テストケースを作ってみよう．
B Obsession with Robots
UDRLで与えられる道筋がショーテストパスかどうかを判定する問題．一度歩いた所をもう一度歩かなければいいと思っていたけど，蛇行運転もショーテストじゃないね．
123456789の順に歩くとき，同じ道は通ってないけどショーテストではない． ..67. 12589 .34..
これに気付かずWA．
C Looking for Order
終了後にダイクストラで解いた．breakを入れるかどうかでTLEがACになる．ていうかなんでここでbreakしていいのかよく分からない…
#include <iostream> #include <cstdio> #include <cctype> #include <cstring> #include <map> #include <queue> #include <algorithm> #include <complex> #include <set> #include <vector> #include <bitset> #define REP(i,N)for(int i=0;i<(int)N;i++) #define MP(a,b) make_pair(a,b) using namespace std; int bx,by; int N; int x[25],y[25]; int dp[1 << 24] = {}; int path[1 << 24] = {}; int dist[25][25]; struct State{ int state; int cost; bool operator<(const State& s)const{ return cost > s.cost; } }; int main(){ while (~scanf("%d %d",&x[0],&y[0])){ N=nextInt(); REP(i,N) x[i+1] = nextInt(),y[i+1] = nextInt(); REP(i,1<<N) dp[i] = 1 << 25; REP(i,N+1){ REP(j,N+1){ dist[i][j] = (x[i]-x[j]) * (x[i]-x[j]) + (y[i] - y[j]) * (y[i] - y[j]); } } priority_queue<State> up; up.push((State){0,0}); while (!up.empty()){ int state = up.top().state; int cost = up.top().cost; up.pop(); //cout << bitset<10>(state) << " " << cost << endl; if (state == (1 << N) -1) { printlineInt(cost); int p = state; int s = path[state]; for (;; s=path[s]){ printf("0 "); //cout << bitset<10>(s) << " " << bitset<10>(p) << endl; REP(i,N){ if (((s & (1 << i)) ^ (p & (1 << i)))){ printf("%d ",i+1); } } p = s; if (!s) break; } printf("0 \n"); break; } if (dp[state] < cost) continue; REP(i,N){ if (state & (1 << i)) continue; int nstate = state | (1 << i); int ncost = cost + (dist[0][i+1] << 1); if (dp[nstate] > ncost){ dp[nstate] = ncost; path[nstate] = state; up.push((State){nstate,ncost}); } for (int j=i+1;j<N;j++){ if (state & (1 << j)) continue; int nstate = state | (1 << i) | (1 << j); int ncost = cost + dist[0][i+1] + dist[0][j+1] + dist[i+1][j+1]; if (dp[nstate] > ncost){ dp[nstate] = ncost; path[nstate] = state; up.push((State){nstate,ncost}); } } break; // このbreakをとるとTLE } } } }
だれか説明してくだしあ．
結果
1490のdiv2からスタート(´・ω・｀)．その代わり次のラウンドはdiv2onlyみたいなので出れるみたい．その次div1onlyかもしれないからぜひ上がりたい．
codeforces用のスクリプト書こうかなぁ．
