UTPC2009
去年は出題側でしたが、今年は解く側で参加。結果は6問で(24)位(1問去年の問題案から使い回しがあるので順位は参考ということで)
A
やるだけ。Accept
B
典型的なDP。ただ点ではなくエッジが通れないので２問目にしてはややめんどう。Accept
C
一人の方の手を固定して、残りの手を9!通り試すだけ。Accept
一瞬モンテカルロとか頭の悪いことを思いついた。
D
最初面倒と思って飛ばす
E
なぜか4桁しかないと思って、探索のコードを書き終わった後に1000桁だということに気づく。
F
50000^2の解法は分かるんだけど、そこから枝刈すれば通るのかなとか思う。
D
とりあえずやれば解けるのは明らかなので書き始める。最初BigDecimalとかを使おうと思ってAPIを読みだしたけどはまりそうだったので、まじめに文字列処理をしだす。
0.000...の部分を除去するところで
replaceFirst("^0\\.(0*)", "")
とするべきところを
replaceFirst("0\\.(0*)", "")
と書いていてはまった。
Accept
E
探索のコードの4桁での出力を眺めていると縮約の回数が隣り合う文字列の取り方によらないことに気づく、ということであまり確証はなかったが先頭から縮約するコードを送ったら通る。
Accept
G
解いていた人が一番多かったので、読んでみる。とりあえず解いている人の人数から単純にシミュレーションして、十分な回数回したらループと判定するというロジックで通るのではという方針で書く。
途中>=とすべきなところを>と書いていてはまる。
Accept
F
とりあえず、25億だったら間に合う気がして送ったら案の定TLE。でその後入力をScannerからBufferedReaderに変更したり小手先の最適化を行ったけど通らない。
オートマトンを作ればいいのではとか思ったけど、どうみてもNFAになるので線形時間だと無理。
残り時間はFとあとI,Kあたりを考えていたが通せず終了。
