cafelier@SRM

SRM493

SRM | 00:34 |

SRM493 の成績・ソース (要ログイン) : AC/AC/- : 撃墜祭り回なので順位はよかった万歳

今回からは方向性を変えて、「こんなコードが本番中に書けたら理想的なんじゃないかなあ、と自分が思うコード」を、そう思う理由とともに並べる参加記になろうと思います。一回で飽きる可能性があります。

450

• 『0～K までの文字が N 文字ならんだ文字列が入力されます。0 の部分をうまく 1 ～ K に書き換えて、"同じ文字の間の距離"の最小値ができるだけ大きくなるようにしてね』
  • K≦7
  • K+1≦N≦50

class AmoebaCode { public:
   // メインルーチン
   int find(string code, int K) 
   {
      int answer = 1;
      for(int D=2; D<=K; ++D)
         if( can(code, K, 0, string(D-1,'X')) ) // 最小距離が D 以上になるようにできる？
            answer = max(answer, D);
      return answer; // できるような D の最大値を返す
   }

   // 「code[i..$) に 1 ～ K を埋められるか？」を再帰的に判定
   // prev には code[i] の直前 D-1 文字を入れて呼び出す。
   // この D-1 文字は避けないと最小距離 D 以上にならないので避けましょう
   map<pair<size_t,string>, bool> memo;
   bool can(const string& code, const int K, size_t i, const string& prev)
   {
      if( i == code.size() )
         return true; // 最後まで埋まった。OK!

      pair<int,string> key(i, prev);
      if( memo.count(key) )
         return memo[key]; // メモ化。すでに見た引数なら覚えてる結果を返す

      // code[i] に入れる文字の候補を列挙
      vector<char> cand;
      if( code[i] == '0' ) // '0' なら 1 から K のどれに置き換えてもいい
         for(int k=1; k<=K; ++k)
            cand.push_back( char('0'+k) );
      else // それ以外なら置き換えられない
         cand.push_back( code[i] );

      bool ok = false;
      for(int k=0; k<cand.size(); ++k) // 候補を全部試してみる
         if( count(prev.begin(), prev.end(), cand[k])    // prev を避けてて
          && can(code, K, i+1, prev.substr(1)+cand[k]) ) // code[i+1..$) も全部埋められればOK
            ok |= true;

      return memo[key] = ok; // メモ化の表に記憶しつつ return
   }
};

• 「最小値を最大 (最大値を最小) にしてね」という問題は脊髄反射で
  • 最小値を 1 以上にできる？ yes
  • 最小値を 2 以上にできる？ yes
  • ...
  • 最小値を X 以上にできる？ yes
  • 最小値を X+1 以上にできる？ no
  • ...
• と、「できるかできねーか、の検査を繰り返しまくる問題」と読み替えてみると良いことが多そう。
• yes → no に切り替わるポイント X が答え。
  • 解の範囲が広い場合は、この切り替わりポイントを二分探索で探すと効率がよいけど、
  • 今回は、どう頑張っても距離 K より遠くはできない＆K≦7と小さいので、1からKまで全探索で十分

• あとは「最小値を D 以上にできる？ yes/no」を判定するコードを書けばいい
  • これは、左から順に 0 のところに文字を埋めていく感じで探索
  • 「距離最小値が D 以上」ということは、つまり、「直前 D-1 文字で使った文字は埋めるのに使えない」ということなので
  • 「直前D-1文字」を引数に覚えておきながら再帰探索
  • メモ化は当然しておく
  • 50(codeの長さ) * 7!(直前D-1文字のパターン数) * 7*(0+1+..+6)(D=1～7の場合の関数内のループ回数) ≒ 3500万
  • なので計算量的には間に合うんじゃないかなー。

• 本番では

int find(string code, int K) {
   for(int D=K; D>=2; --D)
      if( can(code, K, 0, string(D-1,'X')) )
         return D;
   return 1;
}

bool can(const string& code, const int K, size_t i, const string& prev) {
   ...
   for(int k=0; k<cand.size(); ++k)
      if( count(prev.begin(), prev.end(), cand[k])
       && can(code, K, i+1, prev.substr(1)+cand[k]) )
         return memo[key] = true;
   return memo[key] = false;
}

• のような、解が確認できたら即座にreturn、というコードを書いたのだけど、TLEが不安な時はこれはできる限り避けるべきと考える。
• というのは、「最悪ケース」がわかりにくくなってしまうから。

• 「最高速のコードを書く」のが目的じゃなくて「制限時間内に確実に終わるコードを書く」のが目的なのだから
• 「制限時間内に確実に終わることのテスト」ができる書き方をしなければならない。
• 上に貼ったソースなら K=7, N=50, "000...000" が明らかに最悪ケースになるので「そのケースでTLEしないこと」をテストできる。
  • もちろん、即座returnでも最悪ケースがわかる時は、そっちで書いて全然いいと思うんですけど
  • 今回のは K=7, N=50, "000...0007" 辺りが一番キツそうだなあ…と見当はつくけど、時間内にこれが最悪と確信はできてなかったなあ…と

300

• 『N個の石が並んでます。M番目だけ白いです。"連続するK個を選んで並び順をreverse"という操作を、プレイヤー二人が交互にやるゲームをします。白をL番目に持って行ったら勝ちです。最善を尽くすと先手勝ちか後手勝ちか引き分けか』
  • M,K,L≦N≦100万

• 状態数Nで、各状態からNに比例するオーダで手がありうるので、ゲーム木を愚直に探索するとO(N^2)で、これはTLE。
• O(N) でなければ。
  • 数論的に、最小公倍数とか最大公約数とかで勝ちパターンが決まる
  • 実はゲームの構造上 N 手も深く読む必要がなく最初の数手で決着がつく
• というような可能性を考えました。今回は後者。後者だと気づくのに20分くらいかかってしまった…

• 今回のゲームでは、相手と同じ区間を選んでreverseすれば元の状態に戻せるので
  • 1手で勝負が決まる「先手必勝」
  • 2手で決まる、つまり先手がどこに動かしても後手が次の手で勝てる状態になってしまう「後手必勝」
  • それ以外だと、先手は "次の一手では後手はまだ勝てない" ように動かす、後手はそれをundoする。この繰り返しで「引き分け」
• しかない。状態のundoができるゲームだと一般に常にこうなりますね。なるほど。

class StonesGame { public:
   string winner(int N, int M, int K, int L) 
   {
      if( isOneStep(N,M,K,L) ) // M から L に一手でいけるなら先手の勝ち
         return "Romeo";
      for(int x=1; x<=N; ++x)
         if( isOneStep(N,M,K,x) && !isOneStep(N,x,K,L) )
            return "Draw"; // 先手も後手も勝てない場合
      return "Strangelet"; // M からは「Lに一手で行けちゃうx」にしか行けないなら、後手の勝ち
   }

   bool isOneStep(int N, int M, int K, int L)
   {
      int d = abs(M-L);
      if( d<K && (d%2)!=(K%2) )
      {
         int mid = (M+L)/2; // M と L の真ん中を中心に
         int e = mid + K/2; // 右に K/2
         int b = e - K+1;   // 左に K/2 伸ばした範囲をreverseすればMがLに行けるはず…
         return 1<=b && e<=N; // そんな範囲で大丈夫か
      }
      return false;
   }
};

• というわけで、「1手で行けるか」を O(1) で判定する関数があれば、それを使ってそのまま書くだけ
• 「1手で行けるか」は、まあ、色々条件を考慮しつつ書くだけ。
  • 場合によると思いますけど、「1手で行ける。true」という答えを返すときには
  • 同値な数式一発を return するんじゃなくて
  • 「行けるとしたら具体的にどの手で行けるのか（上のコードだと[b,e)をreverseする手）を計算」
  • ＆＆ 「それが実際に可能な解かチェック」
  • とやると、条件見落としをしにくい＆デバッグもしやすい
  • かなーとかなんとか。
  • （最初 return (d<K && (d%2)!=(K%2)); と書いてから、念のためreverseする範囲を計算しとこう、としてやっと条件見落としに気づいた人、談）
  • 他にもこのミスする人多いだろうなーと思って撃墜例用意。4撃墜1不発。

感想

• 300は苦手な問題なのでちゃんと解けた自分を褒めてあげたい
• 450は問題見た瞬間に解法思いついたのに、すごいバグだらけのコードを書いてしまって時間かけ過ぎたのが勿体なかった…