2/27(水) 17:00~22:00でやった
30+100+100=230pt
日程内2位(単独)、一位は異常(最後の年のsemiexp)なので上々
2問目はやるだけだが、この時代では類似の過去問が不十分だったのかもしれない
難易度は12-10-8らしい
本番のフロー
0:05 - 0pt
問題1(ビルの飾り付け)を見る
木でLISをしなさいという問題で、解けるように見えたので考える
愚直に再帰関数を考えるが、答えへの統合が場合分けを要して少し大変だった
そのまま実装して、小課題2を解き30点を得る
EulerTour&Segtreeで出来そうだと予想していたが、式が複雑すぎて不可能と見る
1:13 - 30pt(+30)
問題2(魚)を見る
問題を読んで少し考えると、Segtreeで満点が得られることがわかる
実装が重いことがわかるので、小課題1だけ取って次に行く
1:56 - 40pt(+10)
問題3(JOI旗)を見る
初見では多項式に落ちなさそうに見えるが、AGCをやると多項式に落ちて満点
2:31 - 140pt(+100)
問題2(魚)の小課題2を実装する、もはやバグる要素がなく、30点を得る
2:41 - 160pt(+20)
問題2(魚)の満点を実装して、提出によるデバッグをしていく
3:07 半群に対する敬意が足りず、Segtreeが壊れている(0pt)
3:24 場合分けの漏れにより不正解、小さいケースが誤って通る(5pt)
3:39 オペレータが単調増加でない、小さいケースが誤って通る(55pt)
4:32 ミスに気づいて満点(100pt) - 230pt(+70)
問題1(ビルの飾り付け)を考える
想定解はマージテクらしいが、頭が固いのでHLD&WaveletMatrixなどを考えていた
早々に諦めて終了
反省
・部分点を考えるときは、余計な分岐を避けるため高速化をしない
・半群に敬意を払う
・自明コナーケースの場合分けをやる
・動作に必要な条件を確認する、自明だと切り捨てない