JOI 2020/2021 二次予選 「イベント巡り (Event Hopping)」 に関する記事です． 公式解説 を読みきれなかったので….
問題へのリンク
https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_c
解法
ちょっと不思議な感じで，小課題3 を (私の感覚では) 自然に解くと， それが満点解法にもなっているという… (解説を読むまでわからなかったのですけれど)
ソートして，$S_i$ が昇順になっているとします． ナイーブに考えると，次の DP になります．
- dp[i][j] := i番目のイベントに参加する直前までに参加したイベントの 回数が j であるような方法がある (True/False)
遷移としては，dp[i][j] = True となる j について，
- 町 $P_i$ で行われるイベントで，時刻 $S_i + 1$ 以降最も早いものを i1
- 町 $3 - P_i$ で行われるイベントで， 時刻 $S_i + 1 + D + K(j + 1)$ 以降最も早いものを i2
として，
- dp[i1][j+1] := True
- dp[i2][j+1] := True
と設定することになります．でも，これは $\Omega(N^2)$ なので，間に合いません．
実は，回数を全部見る必要がなくて，各々のイベントに参加するまでに， 最も多くの回数のイベントに参加してきた方法だけ考えれば十分です． ただし，「ある時点までに多くの回数のイベントに参加した方が， 最終的なイベント参加回数が多い」ということは言えません． 次のような例があります．
- $D = 1$, $K = 100$
- $S_1 = 1$, $P_1 = 1$
- $S_2 = 1000$, $P_2 = 2$
- $S_3 = 1150$, $P_3 = 1$
- $S_4 = 1151$, $P_4 = 1$
町 1 から出発して イベント 1 に参加した直後に 2 に移る (方法A) と， イベント2 の直前に，今まで参加した回数は 1 です． 一方，町2から出発する (方法B) と，イベント2の直前に， 今まで参加した回数は 0 で，方法Aの方が多いです． しかし，方法B の方は，このあと イベント2, 3, 4 に参加して最終の回数が3回にできますが， 方法Aは，最終的に2回しか参加できません．
しかし，以下は成り立ちます:
補題
各イベント $i$ に対し，そのイベントに参加する前に参加できるイベント数の 最大値を $M(i)$ とする． 求める答を $X$ とする． 条件を満たしてイベントに参加していく方法 $e_0, \ldots, e_{X-1}$ であって， 任意の $j = 0, \ldots, X-1$ に対して，$M(e_j) = j$ となるものが存在する．
補題が言えれば，DP として，以下のものをとれます:
- dp[i] := $M(i)$
遷移としては，$dp[i]$ が計算できたらば，上で述べた i1 と i2 を取って，
- dp[i1] := max(dp[i1], dp[i] + 1)
- dp[i2] := max(dp[i2], dp[i] + 1)
とすれば良いです．(仮想的に，十分遅く行われるN番目のイベントを考えて) dp[N] が求める答となります．このDPは，$O(N\log N)$ で実行できます．
補題の証明です．帰謬法によることにして，そのような方法がないとすると， $X$を達成するどの方法についても $M(e_j) > j$ となる $j$ があります． 各方法 $\alpha$ についてそのような $j$ の最大値を$j_\alpha$ とし， その最小値を与える $\alpha$ を取ります． すなわち，$M(e_{j_\alpha}) > j_\alpha$ です． イベント $e_{j_\alpha}$ が行われる町を $p$ として， イベント $e_{j_\alpha + 1}$ が行われる町を $q$ とすると， $ p \neq q $ であることに注意します． $M(e_{j_\alpha})$ を与える方法$\beta$ をとり， $\beta$の$j_\alpha$番目のイベント $e$ までの部分を $\beta’$ とします． イベント $e$ が $q$ で行われる場合には，$\beta’$ の後に， $q$ に $e_{j_\alpha + 1}$ まで残り続けて，その後 $\alpha$ と 同じに振る舞う方法を $\gamma$ とします． イベント $e$ が $p$ で行われる場合には，$\beta’$ の直後に$q$に 移り，その後$e_{j_\alpha + 1}$ まで $q$ にいて，その後 $\alpha$ と 同じに振る舞う方法を $\gamma$ とします． いずれの場合にも，$\gamma$ は $X$ を達成する方法であり， $j_\gamma < j_\alpha$ となり，矛盾しました．