UTPC2009

頭が全然回らなくて泣いた。こういう大切の日の前夜は早めに寝るべきだと思った。
速さが足りない。

Problem A: ねこかわいがり

寝坊した。急いで大学に来て、PCの電源を入れた瞬間にコンテストが始まったみたい。
ねこだ。リトバスだ。
念のため、座標系を紙に書いて何度も確認しながら実装した。Accepted.

Problem B: 平安京ウォーキング

またねこだ。
DP. Accepted.

Problem C: カードゲーム

またまたねこだ。今日はねこ祭りか。
Bよりもこちらを先に開くべきだった。next_permutationで瞬殺。

Standingsを見たらDよりも先にEが解かれてた。
Eを読んでみる…よく分からない。Dは面倒臭い実装だ。
ついでにここらで全問目を通しておこう。

F ... 入力サイズを読んで後回しに。
G ... シミュレーションすればいいのか？確信が持てない。
H ... n = 100,000 匹のねこがあみだくじに群がる様子を想像した。事件だ。
J ... TSPっぽい？斜め読みしたせいでねこが100,000匹だと勘違いした。いくらなんでもそれは無理ゲーだ。
K ... ガチ数学だ。逃げよう。
L ... Google Code Jamで似た問題を見た気がする。これもフローか？捨てる。

・・・すぐに解けそうなのが無い。
それはいいとして（よくないけど）、なぜウミとかナミとかフェイとかノーマとかいないんだろう。あれはよいねこゲーなのだけど。
頑張ってD書こう。

Problem D: 単位変換器

接頭辞リテラル埋め込むのがしんどい。テキストエディタに放り込んで置換かけまくった。
実装の手が頻繁に止まる。頻繁にバグる。

隣の席のwatanabe君がBを通せないことを儚んで、辛気臭い曲*1を流してたのだけれども、いい加減鬱陶しくなってきた。
いつもの作業用BGMをヘッドホンで聴き始める。
・・・いや、だめだよ。折角のねこコンテストなんだから、もっと相応しい曲があるでしょうに。

有効桁数調べてー、指数部求めてー、できたー。
ここからが本当の勝負になるだろうと思ってSubmitしたけど、予想に反して一発で通った。やったー。

Problem E: 足し算ゲーム

再チャレンジ。でもよくわかんない。
DP[i][j] := [i,j)桁目の勝者、みたいなことをやるのかな？いや、計算量的に無理っぽい。
もっと簡単に考えてみよう。もしかしたら、どういう戦略を採っても操作回数は一定だったりするのかも？
なんとなくだけど、そんな感じがする。信じて送ったら通った。

このあたりでBGMを止めた。
Ritaは作業用BGMには向いてない。つい聞き入ってしまう。

Problem G: 挨拶の多い本屋さん

シミュレーションすればいいのだろうか。
(店員の数)*(最後の発声からの経過時刻)の空間をメモ化？無理じゃね？

(この間、よく分からなくてProblem Fに浮気したりする)

よく考えたら、店員が発声するタイミングは同じだ。なら無限ループとか起きない気がする。

• • 待て、Sampleにはちゃんと無限ループのケースが入ってるぞ。

このケース紙に書いてみよう。・・・なるほど。2人で互いにイベント駆動してるのか。
こんなことが起きるのは、X>Yの場合だけ・・・だよね？

まとめると、つまりBFSして、1人が2回発声したら無限ループと判定すればいいわけだ。たぶん。
実装だ。

(1時間経過)

やっとできた・・・。
初期化忘れと変数名の書き間違いと条件式の書き間違いと問題文の読み間違いを同時にやらかしたおかげで、すさまじく取りにくいバグを生み出してしまった。
完成したコードはかなり簡潔で、こんなのに1時間以上も掛けてしまったのかと思うと涙が止まらない。
でもまだまだバグ残ってそうだよなぁ、と思いながら送った。通ったー！

Problem F: 天使の階段

O(nm)の自明なDPしか思い浮かばない・・・。
でも音階によって動きがかなり制約されるから、枝狩りを入れつつ上手くDP(というかただのBFS)すれば通るのかな？
と思って書いてみたけど、バグが取れないまま終了。

Final Standings

6 submit, 6 accepted. 21位でした。
DとGが残念すぎます。が、これだけバグ埋め込んだのにRejectを一度も食らっていないという奇跡。
問題の質が恐ろしく高かったです。今は悲しいことに時間が取れないのですが、暇が出来たらリトライしてみます。

*1:「白旗」とかいう曲名らしい。よく分からないけど。