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用のスクリプト書こうかなぁ．
Emacs Lisp for PKU Judge Online and others
id:halwhiteさんがpkuのスクリプトを公開していたので私も公開．poj-modeっていうのは知らなかった…
http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/icpc-online-judge.el#
このLispは外部スクリプトをプロセスを生成して実行します．それにより以下の機能を提供します．
機能
- PKUなどのオンラインジャッジサイトへの自動サブミット
- 上記の結果はポップアップする．
- ファイルを開いたときにテンプレートファイルの自動挿入
- ファイルを開いたときに自動的にサンプル入出力を作成する
- サンプルテスト用コンパイルコマンドの補助(C-c C-cなどに割り当てると便利)
使い方
まず，適当なディレクトリに入れてload-fileしてください．
例：~/site-lisp/icpc-online-judge.elに保存した場合，
.emacsに次のように記述
(load-file "~/site-lisp/icpc-online-judge.el")
(この際，find-file-hookにいくつかの関数をhookします)
次に，icpc-online-judge.elを開いて最初の行，icpc-judge-alistを編集します．
icpc-judge-alistはパラメータリストのリストです．パラメータリストは次の構成になっています．
- スクリプトを適用するファイルの正規表現
- 1にマッチしたとき挿入するテンプレートファイル
- 1のファイル名部分から，問題番号を抜き出す正規表現
- 適用するスクリプト
- 入出力ファイルを作成するときにスクリプトに渡す引数
- サブミットする時にスクリプトに渡す引数
- 1をコンパイルするときのコマンド
パラメータ中では%に続けて特殊文字列が使えます．特殊文字列は次のようになっています．
例えば，pku1000.cppというファイルを1000.in,1000.outでテストする場合次のように記述します．
g++ %f && ./a.out < %p.in | diff %p.out -
これは次のように置き換えられます．
g++ pku1000.cpp && ./a.out < 1000.in | diff 1000.out -
関数は次の通りです．
スクリプト
このlispは外部スクリプトを実行するため，スクリプトが別に必要になります．私の作ったpkuのperlスクリプトはこちらです．
http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/pku.pl
このスクリプトの$idと$passを自分のものに書き換えて下さい．
あまりperl書かないから汚いです．
また，入出力の作成が全然甘いのですが，spojのスクリプトも作りました．
http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/spoj.pl
本当は流行りのcodeforceで作ろうと思ったけど，googleのopenidが上手くできない…
補足
このスクリプトは引数が次のようになっている
*サブミット # ./pku.pl submit 問題番号 送信するファイル *入出力作成 # ./pku.pl sample 問題番号 入力保存先 出力保存先
とりあえず使ってみるなら
icpc-judge-onlineとpku.plを~/site-lisp/に保存，テンプレートファイルを~/icpc/icpc_template.cppに保存，pkuのファイルを~/icpc/pku/1000.cppに保存してみれば動くはずです．
(スクリプト作成者向け)スクリプト作成方法
このlispとスクリプトはexit codeと出力で会話をします．スクリプトの方で
print "hello world"; exit 0;
とすると，emacsのミニバッファにはhello worldが表示されます．またexit 1とすると，hello worldがポップアップします．また，exit 2では，emacsはカレントバッファをスクリプトが出力したものにします．
どうでも良い話
emacs lispの困るところは，マルチスレッドができないところで，昔emacs lispで送信もするものを使っていたのですが，問題のTLEが長い時やそもそもPKUが落ちているときはなかなか結果が帰ってこなくて，ずっとemacsが固まってました．それはとても嫌だったので，lispで固まらない方法はないかと探して外部スクリプトを実行してexit codeでやりとりする方法を考えました．emacs lispがマルチスレッドに対応してくれればこんなにめんどくさいことをしなくてすむのですが．
UVaとかスクリプトを他の言語でとか，誰か作って欲しいなぁ．
SRM466 Div1
ケガからの復帰戦．一つも解けなかったけど撃墜成功してdiv1残れた．わーい．
250 LotteryCheating
- 文字をそんなにたくさん書き換えなくても答えに行くんじゃないかなぁと思って探索してみた．
- 答えをみると最大5なので，大間違いではない．間違いだけど．
- 手元でいくつか試してみたらTLEになるケースを発見．
- いくつか高速化してみたけど全然間に合わない．
- 約数が奇数の数字を最初に求めて，そこに変換してみる方法かなぁと思った．
- でも2 ^ 32個の候補を最初に調べるわけにいかないし…
- ここで約数奇数の法則性を探しに行くことが正解への分かれ道だったのだろうか．
- でも，自分と同じく探索しようとした人は自分がTLEになるサンプルで落とせた．2撃墜．
id:halwhiteさんに探索と思ってはいけないと思うって怒られた(´・ω・｀)ｼｮﾎﾞｰﾝ
500 LotteryPyaterochka
- 見た感じ解ける気がするー．
- でも250が解けてないので，普段解けない500を行くべきかとゆっくり考えられず．
- とりあえずチケットは1 2 3 4 5 6 ... と順番に並んでると考えても全く同じことだとわかった．
- で，あとはwinning numberが一行三つ以上になる並び方…こんがらかってきて250へ戻る．受験生なら解けたよ．きっと．
方針としては，winning numberが5行，4行のときと3行の一部の時はwinnerになれないということを計算する．あとで書いたらかなりシンプルだった．
class LotteryPyaterochka { public: long long nCr(long long N,long long r){ if (N < r) return 0; long long ret = 1LL; REP(i,r) ret *= N-i; REP(i,r) ret /= (i+1); return ret; } double chanceToWin(int N) { return 1.0 - (double)(nCr(N,5)*5*5*5*5*5+ nCr(N,4)*4*nCr(5,2)*5*5*5 + nCr(N,3)*3*nCr(5,2)*nCr(5,2)*5)/nCr(N*5,5); } }
long longにしないと桁あふれするみたい．こういうミスはよくやるので気を付けたい．
1019 Number Sequence
1019をid:keitanxkeitanが２分探索で解いていて，そんな問題だったかなぁとビックリした．自分のを見返してみたらやっぱり２分探索ではなかった．確かに２分探索でも解けるし実行時間は速いけど，こうやっても解けるよーっていう紹介．
概要
112123123412345... という文字列のi(1 <= i < 2^31)番目の文字を求めよ
考え方．
群数列みたいに考えて，1 12 123 1234 ...と分けて，x番目の群はいくつ文字を含むかを考える．x番目の群は少なくともx文字以上含みそうなので，x番目の群までの文字数の合計はx(x+1)/2より多そう．だから，xの範囲は x(x+1)/2 < 2^32 => x < 2^16ぐらいになりそう．多く見積もって2^16ぐらいまで調べればよいので，２分探索しなくても十分間に合う．
ソース内では，numcntがx番目の群の中の文字数を数える関数．含まれる群がわかったら，その群の文字列をstringstreamで生成してその文字列のi - sum(numcnt(1),numcnt(2),...,numcnt(x-1))番目の文字を出力している．
long long?
keitanはlong longを使っていたけど，確かに2^31番目あたりの文字を調べようとすると，それを含む群までの文字数の合計は2^31を超えてしまう．でも，足していくのではなく，引いていけば2^31を超えることはない．(ソース見てください)
数字->文字列変換
数字を文字にしたり，また長い文字列を単語に分ける時はstringstreamが便利．
stringstream ss; ss << 1 << 2 << 3; // ssの中身は"123" string s; ss >> s; // sは"123"
stringを使いたくないときはsprintfとか．
char s[10]; sprintf(s,"%d%d%d",1,2,3); //s は "123"
TopCoderでも"abc def ghi"みたいなstringが与えられて切り分けなきゃいけない時があるので，このときstringstreamを知ってると知っていないでは大違い．
ソース
int numcnt(int d){ int a = d; int ret = 0; int t = 1; int b = 1; while (d >= 10){ ret += t * 9 * b; d /= 10; t++; b*=10; } return ret + t * (a - b + 1); } int main(){ int T=nextInt(); while (T--){ int N=nextInt(); int i; for (i=1;N-numcnt(i) > 0;i++) N -= numcnt(i); stringstream ss; for (int j=1;j<=i;j++) ss << j; string str; ss >> str; cout << str[N-1] << endl; } }
TopCoder SRM464 Div1 550
参加はしていない．
概要
n組の中心座標のペアが与えられる．各組の座標を必ずどちらかひとつ使って正方形をn個描く．最小の正方形が最大となるような座標の選び方をしたときの正方形の一辺の長さを求めよ．
解法
2-SAT+2分探索
2-SATはだいぶ前にPKUで，2-SATで解けるらしいという問題を見たけど，実際に書いたことはなく，理解もちゃんとしていなかったのでこれを機にちゃんと解いた．
2-SATはCNFの節の個数が2個のものを解くアルゴリズム．CNFの節をimplicationの形に書き換え，各変数を頂点，implicationを辺とするグラフを作成する．
そしてのような矛盾が生じないかを確認する．この例では，pか~pのどちらかが成田っていなければいけないのに，どちらでも矛盾が生じてしまう．
この問題では，i番目の座標ペアをとすると，piaとpibは同時に成り立ってはいけないので否定の関係にあり，またpiaが成り立つときpjaが成り立たない事を
と表せる．この通りにグラフを生成し，矛盾が生じるかどうかを調べればよい．
この問題は頂点の数が少ないためWarshall-Floyd(O(n^3))でも大丈夫．高速化が必要な場合は強連結成分分解を用いてO(n+m)(mは節の個数)でもできる．以下はワーシャルフロイドを用いて実装した．
class ColorfulDecoration { public: vector<int> xa,ya,xb,yb; bool check(int mid){ int n = xa.size(),N=2*n; bool graph[N][N]; memset(graph,false,sizeof(graph)); REP(i,N)REP(j,N){ int ii = i/2,jj=j/2; if (ii == jj) continue; int x1,y1,x2,y2; if (i & 1) x1 = xa[ii],y1 = ya[ii]; else x1 = xb[ii],y1 = yb[ii]; if (j & 1) x2 = xa[jj],y2 = ya[jj]; else x2 = xb[jj],y2 = yb[jj]; if (abs(x1-x2) < mid && abs(y1-y2) < mid){ graph[i][j ^ 1] = true; } } REP(i,2*n) graph[i][i] = true; REP(k,2*n) REP(i,2*n) REP(j,2*n){ if (graph[i][k] && graph[k][j]) graph[i][j] = true; } bool flag = true; for (int i=0;i<2*n;i+=2){ if (graph[i][i+1] && graph[i+1][i]) flag = false; } return flag; } int getMaximum(vector <int> XA, vector <int> YA, vector <int> XB, vector <int> YB) { xa = XA; xb = XB; ya = YA; yb = YB; int l = 0,h=1000000001; while (l < h){ int mid = (l + h) / 2; if (check(mid)){ l = mid+1; }else{ h = mid; } } return l-1; } }
