tsubosakaの日記

Google Code Jam Round 1A

00:50

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を解こうと思い全探索のコードを考えたけど、いろいろはまって終了