東京大学プログラミングコンテスト2012に参加してみた
UTPC2012にネット上から参加してみました。
A - 2012年12月02日
与えられた日付の月、日を並び替えて年数と同じに出来るかを判定する問題。始めは指示通りに実装しようかと思ったけど、数字の順番は関係ないので数字の種類だけ覚えておけば良い。自分にしては珍しく早く解けました（それでも12分くらい。トップクラスの人たちは2〜3分）。
ソースコード
B - 残像に口紅を
段々文字が制限されていく生成規則で作った文字列から制限文字の順番を求める問題。
始めはよく意味が分からなかったが、よく問題を見てみると単純に文字列を後ろから見て制限文字を決めていけばよさそう。AC。
ソースコード
2問解いて約27分。自分の中で過去最高の早さです。
E - 選挙
衆院選、都知事選に絡められたタイムリーな問題。比例代表制選挙で各政党の票数と最低議席数が与えられた時に条件を満たす最低総議席数を求める問題。
普通にやるととても無理だけど、確かこういう問題は「議席数がMで条件が成り立つ」をMがあり得る範囲で二分探索すれば出来た気がする・・・。
そう思い、さっそく実装するもWA。小数を扱う問題なので、ここが問題なのかと思い、ネットで調べながら噂には聞いていたBigDecimalクラスを使い実装し直し。ただ、無限の小数はさすがに扱えないみたいだったので、桁を1000桁で実装。いくつか通るケースが増えたもののWA。
もしかして二分探索の範囲が狭いのかと思い（0〜10^11）、広げてみたものの（0~10^18）駄目でした。
自分の中では実装は間違っていない気がするんですが、どこか間違ってるのかしら？？それともまさか小数じゃなくて分数の形で厳密に扱わないといけないのか？？結局最後まで頑張っても通りませんでした。
ソースコード(WA)
諦めた時点で4時間くらい経過してた。
C - 森ですか？
完全グラフからいくつか辺を取り除いて新たなグラフを作り、閉路があるかどうかを判定する問題。単純に各頂点に対応する配列を作り、頂点どうしの辺の有無を表すのは頂点数が10^5もあるので無理っぽい。試しにJavaで10^5*10^5の配列を作ってみたらMLE。
10^10がデータ構造に単純に表現出来ない以上、多分取り除く辺（高々10^5）を工夫してMapとかで作っておけば出来るのかな？
よく分からなかったので部分点（頂点数 <= 100）を狙いに単純に実装。「各頂点から、来た道を戻らずに全ての頂点を見に行き、全て今まで見たことが無ければ閉路が無い」と判断出来る。
なんとか部分点は取れました。
ソースコード(WA)
以外の問題は解いていません。解法を考えてたのはH（スケジューリング）とI（複数点間の最短路）。Hは貪欲法かDPで解けそう。Iの最短路は部分点の方は全点間の最短路を計算するワーシャル・フロイド法かなーとか思ってましたが、今考えると計算量足りない？？
解けた問題は12問中2.5問で最終順位は94位でした。
来週は早稲田のコンテストがあるとか。参加出来たらしたいですね。
