2010-05-23
Google Code Jam Round 1A
Problem A
- 問題読む。実装問題っぽい
- 左のスコアを見るとProblem B,Cが5ptだったのでそっちへ
Problem B
- DPっぽいけど、思いつかないProblem Cへ
Problem C
- AとBの値が小さい場合のケースを出力して傾向を見てみる
- A >= 2 * Bと複数の選択肢があるときは勝てるっぽい、なんとなく証明もできる
- 選択肢がないときは(A - B , B)を評価してやればよい
コードとしては以下のようになる
static boolean win(int A , int B){ if (A > B) { return win(B, A); } if (A == B) return false; if(2 * A < B){ return true; } return !win(B - A , A); }
- 通ったけど5ptなのに結構順位が上がったと不思議に思ってみると16ptに配点が上がってた
- せっかくなのでLargeを考える、Aを固定したときにBを動かして勝ち負けをみるとtrue,...true,false,...,false,true....となることが解る。
- 変化点を二分探索で求めてやる方針で解く、これだと計算量はO(A * log^2(A))となる
Aを固定したときにB1...B2までの範囲で勝ちの数を求めるコードは以下のとおり
static long count(int A , int B1 , int B2){ if(B1 > B2)return 0; if(A <= B1){ if(win(A, B1))return B2 - B1 + 1; if(!win(A , B2))return 0; int left = B1; int right = B2; while(left < right){ int mid = left + (right - left) / 2; if(win(A , mid))right = mid; else left = mid + 1; } return B2 - left + 1; }else if(B2 <= A){ if(win(A, B2))return B2 - B1 + 1; if(!win(A, B1))return 0; int left = B1; int right = B2; while(left < right){ int mid = left + (right - left) / 2; if(!win(A , mid))right = mid; else left = mid + 1; } return left - B1; }else{ return count(A, B1, A) + count(A, A, B2); } }
Problem B
- Problem Aにいけばいいものをなぜかこっちへ
- とりあえずsmallを解こうと思い全探索のコードを考えたけど、いろいろはまって終了
コメントを書く