JOI Open 2021

結果

100-100-10 (210)

詳細
1:48 28-0-0
2:28 28-100-0
2:58 28-100-10
3:55 100-100-10

思考

A（1 周目）

小課題 2 から考えた。区間に対する操作をしながら情報を取得するので、遅延 Segtree で解けそう。考えると、各区間に対して

• 正しい文字列において、その区間内に 'J', 'O', 'I' がそれぞれ何個あるか
• その区間において、今の文字列と正しい文字列が何文字一致しているか

を持ってやると、merge は各要素ごとの足し算、update は一致する数を「変更先の要素の数」に変更すれば良いので、遅延 Segtree に載る。初めて非再帰遅延 Segtree をソラで書いたので割と時間を食った。 小課題 3 以降は分からなかったので一旦飛ばした。

B（1 周目）

明らかに DP ぽいのでその路線で考える。まず dp[i][j] := i 個見て、一番 A が大きいのが j の時の最大値 みたいなのが思いつくが、明らかに無駄がありそう。ちょっと考えると、A の Max が更新されるところを管理するのが良さそう。dp[i] := 最後に A の Max が更新されたのが i の時の最大値 と定義すると、dp[j] ← dp[i] + 1 と遷移できる条件は

• A[i] < A[j]
• i < k < j, A[i] >= A[k] を満たす k を全部選んだ時、i から j までの間で、差が D 以上になる場所がない

と書ける。配る DP をやると、自明に O(N²) で解ける。

簡単枠ぽかったので、実装せずにそのまま満点解法を考えた。上の条件をじっと睨むと、i から遷移できるのは「ある区間内にありかつ A[i] < A[j] を満たす j」 みたいになるので、この区間を求めたい。これは、A[i] が小さい順に i を見ていって、map とかで差が D 以上になる場所を管理してやるとわかる。それさえ分かれば、同じように A の小さい順に dp の値を見ていくと、区間 Max 一点取得の操作に帰着される。もっと上手い方法があるかもしれないが、A で遅延 Segtree を作っているのでそのまま流用する。30 分で解けたのでよかった。

C（1 周目）

色々考えてみたがなんかよく分からないので、とりあえず小課題 1 を解く。これは全ての組み合わせで対戦させて、勝利数順に並べたのち、勝利数 1 同士・N-2 同士を対戦結果を元に並び替えれば良い。考察がそこから膠着したので 2 周目に行く。

A（2 周目）

交配によって作れる条件を考えたいが、なんの特徴量も掴めないので、とりあえず実験コードを書いて、色々な初期条件に対して作れる遺伝子を全列挙してみる。すると、どんな初期条件にしてみても高々 9 個しか出てこない。まさかとは思ったが、作れる遺伝子を全列挙した後に全てに対して小課題 2 と同じことをやると、満点が得られた。拍子抜けした。9 個で抑えられる証明は与えられていないです（そもそも高々 9 個なのか？）。

C（2 周目）

1 時間くらい考えて、二分探索とか色々なものに思いを馳せてみたもののよく分からず。 ここで 10 点超えられるかで上位に入れるか分かれそうだなあと感じたがやはりそうだった。