読者です 読者をやめる 読者になる 読者になる

ICPC2010日本国内予選

まだ参加資格はないけれど、問題をリアルタイムで解いてみました。
A, B, Cの三問解きましたが、Sample Inputに対して正しく答えを出力しただけなので
実際のテストケースで落ちる可能性は十分あります。

Problem A

さくっと実装。
所要時間:10分

Problem B

迷路探索。実装ゲーだった気がします。
バグに嵌って時間を費やしてしまった。
所要時間:35分

Problem C

動的計画法
最初に全部計算してO(n^(4/3)+テストケース数)くらいになりました。
問題の意味を誤解してたので無駄に時間を食ってしまった。
所要時間:20分

Problem D

最初問題の意味が分からん&実装が重そうだったので飛ばしました。
競技時間終了前-5分頃に問題の意味を理解しました。

Problem E

グラフ。この問題に最後まで取り組んでいたけど出来ませんでした。
最初にゴールドにたどり着けないノードを深さ優先で計算しておいて、スターから「現在のノードから行けるノードの中でゴールドにたどり着けないノード以外で文字列が一番辞書順で早いものを辿る」という形で深さ優先すればいける気がしましたが、閉路の扱いと「辞書順で早いけど接頭辞になってるだけ」の形に困りました。うーん。少なくとも紙とペンを用意して置くべきだった…。

Problem F

Problem G

問題だけ見ましたが難しそうですね。
それぞれ編集距離(たぶん)と幾何です。

けつろん

仮に全部テストケースを通過したとして3問ACなので、アジア地区予選に進めるかと言われたら難しそうなところですね。
来年からICPCを選手として受けることになりそうですが、その時は3人居るので、いい結果が残せたらいいなと思います。
ICPCに参加されたみなさんお疲れ様でした。