JOI2019/2020 本選 の簡単な解説(Cまで)

まだ公式が出てなさそうなので、簡単に

A - 長いだけのネクタイ (Just Long Neckties)

B _ {i} と差を取るのは A _ {i} か A _ {i + 1}の2パターンしかなくて、それは自身より前に取り除かれたか後に取り除かれたかで決まる

よって取り除く位置を全探索して、二つのmax配列を持ってセグ木やら左右maxやらでみていけばいい

B - JJOOII 2 (JJOOII 2)

これは結局取り出すsubsequenceの左右のindexの幅が最小になればいい

よってJをK個取る位置を全探索してやると、後はOとIはできる限り左に詰めるのが良い

自分はqueueを6本もって実装した。

C - スタンプラリー 3 (Collecting Stamps 3)

dp[i][j][k][l] := l(左右)からきて、i番目からj番目まですでに見た時、k個スタンプを押したときの最小の時間

で後は適当にその通り遷移。時間がどうやってもdpの配列に持てないからこうするしかないね。