Hatena::Grouptopcoder

Tayama@TopCoder

2011-01-14

SRM493 Div1

06:21

はてなダイアリーがあるのでわざわざTopCoder部に入る必要性を今まで感じていなかったのだけど、最近TopCoder部の人口が増えてると聞いて、折角なので流れに乗ってみることにしました。


  • Petrを始め、3人のtargetがいる恐ろしい部屋に放り込まれた。
    • がたがた震えながら試合開始。

300: StonesGame

  • DPしようかと思ったけど、状態がループするのでややこしい...。
  • ...ループ?
  • ある操作に対して、その逆操作は必ず可能なので。
    • 最初の1手で勝てれば先手の勝ち。
    • 最初の1手で決まらなくて、かつ最初の1手で打てるところが1ヶ所しかなくて、かつそこから後手が勝てるのなら後手の勝ち。
    • 2手で決着しなければ、直前の相手の操作の逆操作を行うことで、先手も後手も決着を無限に引き伸ばせるのでDraw。
  • こんなad-hocな方針でいいのだろうか。怖いけどとりあえず書こう。
  • bool cango(int N, int K, int src, int dst){ return srcにある白石を1手でdstに持っていける? } が書ければ幸せになれる。
    • srcとdstの距離が十分近いことと、距離やKの偶奇を見ればいいのかな?
      • いや条件が足りない。例えば K が大きいときに、白石を右端からその1つ左へ持ってくことができない。
        • うーむ、これはバグらずに書く自信がないぞ。
  • よく考えたら、可能な白石の移動先を O(N) で全列挙しても間に合いそうだ。
  • 書いた。最後のケースだけfailed。
  • ...
  • あ、最初の1手で打てるところが複数あっても、それら全ての場所から後手が勝てるのなら後手の勝ちなのか。
  • ループを追加す...いや待て、それは O(N2) だろう。
    • さっくり書いて答えが合うことだけは確かめたけど。
    • やっぱり cango を書かなければならないのだろうか...。
  • いや待て。
  • (1手でdstに行けるところ) includes (先手の最初の1手で行けるところ) の場合のみ後手の勝ち。
  • 逆操作が必ず可能であることを踏まえると。
  • (dstから1手で行けるところ) includes (先手の最初の1手で行けるところ) の場合のみ後手の勝ち。
  • 集合同士の包含判定は std::includes() を使えば O(N) でできる!
  • あっという間に書けた。submit!

450: AmoebaCode

  • 7次元DPしか思い付かない。
  • 微妙にTLEしそうだなぁ、と思いながら書いてたらCoding Phaseがもう終わりそうだったので諦めた。

Challenge Phase

  • 300を落とす人はあんまりいないと信じて450を見てみる。
    • 答えを線形探索しつつバックトラックしていた人がいたので、{"000...011", 7} で落とした。
      • これぐらいなら自明な枝刈りで弾けるけど、それをやってないことは入念に確認した。
      • 後で知ったけど、このコードは {"000...0", 7} とかを3回ぐらい防衛してたらしい。紙一重だった。

System Test

  • 300通る。
    • Room3はテスト終わるの早いね。感動した。
  • oxx +50.0 196.55 96th 1633 -> 1734
    • Easyをのんびり確実に解いて、たまに1撃墜でもしていれば、MediumとHardは開かなくても1700台を維持できるのかな。