JOI2018本選 参加しました
※これは本選問題の考察がどうのこうのについての記事です。本選中の宿泊などの生活については一切触れません。そういった部分は参加記もどきにまとめました。
本選の結果はまだ分かりません。ボーダーも分かりません。なので少し怖いです。
問題
1問目
以前自分がyukicoderで作った集合に分けようという問題と解法がほとんど同じなのでスッと6-7分くらいで満点で解けました。
2問目
重さの最大値と最小値を決めたらその範囲の重さの美術品は選べることに気づくまで数分かかりました。累積和をパッと思いつき、開始30分くらいでO(N^2)を実装して50点を得ました。
開始2時間くらいで最小値を固定して最大値を動かす探索を高速にやればいけそう、と思ったのでセグ木を使って実装したら10点しか取れませんでした。で、開始から3時間55分くらいでバグの理由に気づき、修正して提出したら100点取れました。ギリギリセーフ。
(最小値を左から右ではなく右から左に動かせばこの問題の満点解法にセグ木は必要ない)
3問目
小課題1(愚直全探索)をbitを使って全列挙しました。TLEしました。意味がわからない
4問目
小課題2(経路復元Dijkstra)を解こうとして案の定バグりました。
Dijkstraでバグるのはいつも通り()
5問目
問題は見たけどプログラムには全く触れませんでした。今見たら、愚直にやれば小課題1と小課題2(計12点)は通りそうでした。
高速ゼータ変換とか知らないし
結果
1問目と2問目を満点AC、2完200点でした。
ボーダーは(200, 300]の範囲だと思うので、落ちるのが確定しました。
