SRM482

インターンが無事終了したのでTopCoderにも復帰。
しばらく競技プログラミングから遠ざかっていたら、随分と腕がなまっているらしいことがICPCのチーム練習で発覚しました。リハビリリハビリ。

250: LockersDivOne

• サイズはそこそこ。下手に実装すると死ぬだけのシミュレーションかな。
  • vectorとeraseを使うと間違いなく即死。
  • bool配列はどうにか間に合うのかな？でもちょっと面倒かも。
  • あ、listでいいんじゃね？
• 書けた。最大ケースで 0.8 sec. submit.
• どうでもいいけど、list に EACH マクロ (iteratorをbeginからendまで回すfor文) が使えることに何とも言えない便利さと気持ち悪さがありました。
  • なんで気持ち悪いんだろうとしばらく考えてたのですが、そうだ、C++のくせにどことなくDuck Typingっぽいからだ、と気がつきました。

500: HanoiGoodAndBad

• Daveステップ目の形がどんなものかは愚直にシミュレーションしても十分間に合うので。
• つまり Earl の形が何ステップ目かを求めるのがキモなわけですね。
• ...って、同じような問題を考えたことがあるのだけど。
  • 「普通のルールのハノイの塔の途中経過が与えられます。何ステップ目か求めてね」という問題。UAPC2011か何かに出すつもりでした。
    • この問題はもう使えないなぁ。残念。とっとと出しておけば良かった。
• 気を取り直して、この問題のために用意した解法がそのまま使えないだろうか？
  • 一番大きな円盤がどこにあるかによって、上の部分塔が動かされた回数が分かるので、それに部分塔を動かすステップ数 (式から求まる) を掛けて足す。
  • 動かし途中の部分塔のステップ数は再帰的に求める。
• がりがりがり。ねむい。かけた。
• とんでもない値が出てきたぞ・・・？
• ...
• あ、一ヶ所 return が抜けてて評価するだけになってる。修正。
• ...近い値が出てきた。けど、サンプルが全部 -2 から 6 ぐらいずれてるってどういうことだ・・・？
• うーむ。方針は合ってるに違いないけど。
• ねむい。あたまがまわらない。ねたい。
• ...
• ...
• あれ？高さ N の塔のステップ数が 3^N になってる？
• 再帰の終了条件もおかしい・・・。もう1段掘らないと。
• なんかサンプル出てきた。これでいいのかな。
  • Mediumなんて滅多に解けないので不安になる。
  • 一応最大ケースを突っ込んで確認。よし合ってる。
• submit!
• 見直しするようなところもあんまりないし、1000は無理ゲーなのでのんびりまったり。

Challenge Phase

• おいしいところは自分が開く前に他の人に持っていかれました。
• 500でちょっと独特なことをやってる人がいた (それどころか私を落とそうとして失敗してた) 人がいたのですが静観。
  • 最後の最後で赤い人に落とされてました。
• プラマイゼロでフィニッシュ。

System Test

• oox 439.29
• 1390 -> 1550
• 黄色復帰。やったー。
• 次の課題は実装・・・というよりデバッグの遅さをどうにかすることかな。