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
問題だけ見ましたが難しそうですね。
それぞれ編集距離(たぶん)と幾何です。