square869120Contest #6 参戦記
参戦しました。 Paris–Roubaix 見つつしかも酒が入っている状態でしたが 1865 点で 93 位。600 点問題取れたしまずまずだったのではないでしょうか。
マラソン問題はじめてでしたが楽しいですね。時間があっという間でした。ただし解を改善しようしてバグを出して改善できなかったのでもっと実装力をつけないと。
パフォーマンスも計算してくれたみたいです。
これによるとパフォーマンス 1902。青領域に突っ込んでいたようです。
感想
A 問題
全部足した後で割る。
B 問題
スタートとゴールの候補は品物を買う場所しかない。全探索。
C 問題
H * W の中に
- 1 -> H に行ける道がある
- 横一列通れる列がある
を両方満たせば OK。なのだが 1 -> H の探索でポカ (探索済みのマスも探索していた...) をやって TLE を出す。
D 問題
- 同じ位置にある雪玉は融合必須
- 雪玉は大小あるときには小を動かすべし
- つまり、融合場所はどちらかの雪玉がある位置
- 雪玉を逆方向に動かすと確実に減点
により、初めから雪玉が配置されている位置での、左から雪玉をあつめた時の半径と右から雪玉をあつめた時の半径を計算して、和が最大になるのところをとればよい。
ただし和を計算するときには from_left[i] と from_right[i + 1] の融合になることに気を付けること。(左右から i に来た時の値は i 番目の雪玉が 2 重カウントされる)
E 問題
ぱっとみて方針がたたなかったため I 問題を優先した。
I 問題
- 縦に一行おきに全部埋める + 適当に横につなぐ
- 横に一行おきに全部埋める + 適当に縦につなぐ
から得点の高いものをとるという適当実装を投げつけておいて部分点を取った。
そのあと付け替えによって解の改善を試みるも、バグが取れずに改善できず...