UTPC2008
結果としては12問中9問解いて、３位
順位的にはまぁ満足だけど、解けなかった３問中２問は解けそうな問題だったので、解きたかったなぁ
以下当日の流れ
A
やるだけな問題だったので瞬殺して次へ…
と思ったらWＡ
問題ID間違えてたorz
問題ID直して今度こそ次へ…
と思ったらRE
えぇーーーさいたまトラップかと思って問題文を読み直しても原因が分からない
ひとまずもう一回Submitしたら今度は通った
ただのミスジャッジだった
00:04:25 Accepted
B
ルートまでで割ってみるだけ
00:13:41 Accepted
C
全探索した
00:22:31 Accepted
D
移動できない場合に向きを変えるのを忘れていてWA×2
00:42:54 Accepted
E
一番長いのを最小化と勘違いして、二分探索を組んでしまったorz
組み終わってから解が合わないことに気づいて、問題文よくみたら総和を最小化だったorz
家の間隔をソートして大きいほうから削除していくだけ
00:52:53 Accepted
次のFが問題文の意味が最初理解できなかったので、ここらで他に簡単な問題がないか目を通すことに
Gはいきなり化学ぽい図があったのでパス
HとIはグラフぽかったのでひとまずパス
Jは構文解析ぽかったのでパス
Kは探索ぽかったのでパス
Lは最終防衛問題ぽかったのでパス
というわけで諦めてFをやることにした
F
ちゃんと問題文を読んだら理解できた
2048文字1024和音までの部分を、間違えて2048和音までにしてしまってWA×2
01:23:00 Accepted
G
化学ぽい図でちょっと引いたけど、ちゃんと問題文読んだらただのDPだった
01:37:16 Accepted
次に何を解こうか悩んでいたら、Kだけすでに解かれていたのでKに挑むことに
K
探索しなくても場合分けでいけそうだということに気づいて場合分け開始
何回かWA出した結果、
- 最初の二点のどちらかが目的地のときは0
- 最初の二点両方から電波が届くときは1
- 最初の二点の片方から電波が届くときは2
- 最初の二点両方から電波が届く場所に目的地に電波を飛ばせる点があれば3
- 残りは4
という結論に至って今度こそ通るだろと思ったら、またWAorz
ここで何を思ったか、場合分けで悩むより、最高４までなんだから探索したほうが早い気がしてきて探索を組み始めてしまったorz
で、探索してもWAorz
よく考えたら二点がたがいに電波が届く位置関係のときその直線上のどこにでも置けることをすっかり忘れていた
Eclipseのヒストリーから場合分けバージョンのソースを復活させてちょっと修正したら通った
WA×8
03:51:49 Accepted
