はじめに
参加してきました。 ABCDEの5完+f部分点で520点でした。
ここに本番の流れや解説、完走した感想をまとめます。
本番の流れ
開始から10分でABCを順番に解いていきました。 0WAでした。
次にDを解こうとするとWAが生え、(解法が同じで通した人がいるため実装ミス？)改善するのがつらかったためUnion-Findで殴りました。
EはO(N2)のDP解しか思いつかなかったためそれを実装していた所、1次元DPにしても問題ない事がわかりそれをしました。ここまでで42分でした。
Fは満点解がわからなかったため部分点狙いでO(N3*4N)ぐらいのものを生やしたのですが、それの実装を無限にバグらせ続けて険しかったです。
開始100分弱の辺りで投げ、6点を取りました。20点分のパートでMLEを出していたためDP配列の次元を落として(空間計算量のみを落として)改善、20点を取る事ができました。
その後は何もわからなかったため80分間椅子に座り続けました。とても疲れました。
(解けた問題の)解説
現時点ではまだ問題文が公開されていないのですが、気合で読んでください。
1問目
算数ができないので愚直にループを書きます。
2問目
O(NM)かけた愚直シミュレーションでいいです。2020に番兵を置くと実装が楽です。
3問目
1次元DPをします s[i]とs[i+1]が異なるならdp[i+2]=max(dp[i]+1,dp[i+2])をすればよいです。
4問目
両隣より高い or 両隣より低い地点だけを気にしながら累積和をすればいいような気がしましたが、WAでした(実装で失敗してたみたいです)
地点を高さ順にソートしてからUnion-Findに突っ込んで、海面の高さを小さい方へ動かしながら[海面の高さより高い地点にある島の数] - [Union-FindのUnite操作で併合されたものの数]の最大値を取るといい感じに解くことができます。(標高が0の地点が陸地になる事はないので、そこだけ注意)
5問目
「dp[i]:i番目まで見た時の最大値」みたいなよくあるDPをしようとすると考えるた場合、LiとRiの制約は「[Li,Ri]にあるものを選んだ場合はdp[Ri+1]に飛ぶ」みたいな感じに置き換える事ができるのでそのまま1次元DPをする事ができます。
飛ぶ先の地点について事前計算をしないといけないため、区間max + 区間更新(ただし更新前の値の方が大きい場合は値を更新しない)を行えるセグ木を貼りました。(実際は累積maxを取るだけで大丈夫らしいです。)
6問目
部分点(小課題1,2の20点分)しか取る事ができなかったため、それについてのみ解説します。
小課題2はNが10以下、Aの最大値(表記が面倒なのでこれに1を足した値をAとします)が3以下と相当緩くなっていて、これの制約でなら"どの国の参加者を何人置いたか"(状態数がAN)をDPの状態に保持する事ができます。
また、席の左側から埋めていく事を考えると保持すべきなのは前述した情報 + 一番右側にいる人の国籍 のみで済む事もわかります。
そのため、「dp[i][j][k]:左からi個目の席まで埋めて一番右側にいる人の国がjであり"どの国の参加者を何人置いたか"の情報がk」でDPをする事ができます。
遷移をさせる際右端の席に入れる参加者の国籍を全探索するため、計算量はさらにNがかかってO(N3*AN)となります。(席の数は最大で3Nとなるのでそれの定数倍もかかります)
これは見た感じかなりヤバそうなのですが、dp配列の空間量を1つ落としたりするとなんか通りました(計算量解析ができません…)
完走した感想
思ったより順位が高かった(おそらく3位タイ(？)で把握してる範囲で同点がたくさん)のでうれしかったです。ここまで取れば流石に予選落ちはないはずです。
かなり良い得点を取れたため自分自身に自信がつきました。といっても今回は運が良かった方(問題セットがぼくに合っていた)なので、気を抜かず本選まで精進を続けていきたいと思います。
ボーダーは385±30点程度になると思っているのですが、実際はどうなるのかとても気になっています。弊の人や知り合いがたくさん通っている事を願います。
(ボーダーが521以上でなければ)本選もがんばります。ここまで見て頂きありがとうございました。
