TCHS10 Round 1
今年も始まりました。オンラインで4ラウンド。
Room
Room 8
neal_wu部屋。おわた
500
冷静にswapするだけ
250
やるだけ
1000
冷静にDPするだけ
Challenge
ぱっと見でわかるものは全部持って行かれた
System Test
まあ
Result
245.81 + 485.31 + 892.09 + 0.00 = 1623.21
6位 (部屋2位)
TCHS: 2022→2039
3問とも一度はバグを埋め込んでいたのは酷い。
SRM 462
Room
Room 17
赤少ないし青多いしおいしそう
250
なぜか整数の(1/整数)乗しかない、と思い込んで組み出してからそうでないサンプルの存在に気付き、大きく出遅れ。二分探索に書き換え。コーナーケースがいろいろありそうな気はしたが、1桁になるケースだけ場合分けしておいてあとは大丈夫ということにしてsubmit
450
期待値の線形性は偉いです
確率だけS回分計算しておくと楽かつ速いですね
しかしこれだけのコードに16分orz
1000
状態100*(辺の数)にしてBellman Fordっぽく
TLEが不安だったが大丈夫だろうということにして提出
Challenge
250でreturn -2にだけひたすら着目したら5つ落とせた
500で/(N-1)にだけひたすら着目したら2つ落とせた
自分の250は落とされた
System Test
450と1000は通った
250は1=1+xとかで解ありと判定したのが原因、大量の人がそれで落ちた模様
Result
0.00 + 349.57 + 625.01 + 350.00 = 1324.58
5位 (部屋1位)
2989→3033
こういう250は落ちるのはしょうがないですがTopCoderらしくて良いと思います。残り2問が難しめのときにやられると困りますが今回みたいなセットだと楽しいです。いやまあもっと注意力つけなさいって話ですけどね。
SRM 461
Room
Room 2
普通
300
やるだけ
500
普通にDijkstraで通るはずと信じてsubmitしたがTLEorz
とりあえず適当な枝刈りつけてresubmitしておいた
950
サイズ40の時点でやることがわかるが組み終わらなかったorz
500よりこっちからやればよかったと後悔
Challenge
終点だけ離れているケースを作ってみたら自分のもTLEしたのでやけになって投げまくったら2成功4失敗で悲しいことに
System Test
もちろん500は落ちる
Result
265.41 + 0.00 + 0.00 + 0.00 = 265.41
93位 (部屋4位)
3064→2989
こんなんで一応2桁順位なのねえ。ひとまず3000さようなら。
500は結局定数倍悪い実装をしていたのが原因。ヒープ自前にしたら結構速くなった。状態50*2000でない解法をやったらもっと速かった。座標の上限増やせばよかったのにー、とは思いましたが500なので仕方ないのかな
SRM 460
Room
Room 5
赤5人部屋、しかも名前が線対称なあの方と同室だったので撃墜辛いかなぁと予想
250
枝刈り探索が想定されているだろう、とは思ったものの、なぜか怖気づいてしまったため血迷った結果無駄に包除原理を駆使して計算した
500
見るからにDP
推移の計算適当にしすぎて合わなかったが適当に修正したらサンプル通ったので出した、最大ケースの確認を忘れてたしメモリも相当危なかった
1000
わかりません
Challenge
250で書き写してみたら偶然落とせた
System Test
通った
部屋残り全部通ってた
Result
221.31 + 376.19 + 0.00 + 50.00 = 647.50
6位 (部屋1位)
3024→3064
250で10^3のDPの発想はなかった……
Top10入りが見えてきた気がしなくもないです。
