はじめに
「Cueing」writer の kotamanegi です。裏テーマを出題1日前に爆破 (偶然の一致？) されました。
簡単枠に見せかけた沼枠を目指しました。中難易度と高難易度の橋渡し的な問題となっていたら嬉しいです。
解説
まず、整数秒目ではない 0.5 秒目などのタイミングでボタンを押すことはないとしてよいです。なぜなら、ボタンを押すタイミングを整数秒目にずらしても損しないからです。
時間ステップ $t$ を、$t-1$ 秒目から $t$ 秒目までの時間帯とします。この時間ステップの概念を使って元問題を区間スケジューリング問題に帰着します。
観客に聞こえる音の制約から、各時間ステップ $t$ の各スピーカーの状態の制約が以下の3つに定まります。
- 制約 A: スピーカーから音が必ず再生されている
- 制約 B: スピーカーの状態はどの状態でも良い
- 制約 C: スピーカーが必ず止まっている
このうち制約 A が一つ以上含まれるような制約 A + 制約 B の区間を取り出すことを考えます。制約 A の個数は $Q$ 個であることから、このような区間は高々 $Q$ 個です。
制約 A + 制約 B の区間を取り出した後は、以下の部分問題を各区間について解けば良いです。
区間 [$L$, $R$] が与えられます。
長さ $T_s$ の区間を追加することがコスト $1$ で、 長さ $1$ 以上 $T_s$ 未満の区間を追加することがコスト $2$ で可能です。追加した区間は重複部分を含んではなりません。
制約 A から生成される区間 [$c_i$, $c_i + 1$] を全て追加した区間で被覆するときに必要なコストの最小値を求めてください。
以下に入力例と、そこから区間への分割方法を示します。
2 5
2 2
1 2 1 1 2
------
スピーカー 1 から生成される区間: [0,∞]、[0,1] と [2,3] と [3,4] を被覆する必要がある
スピーカー 2 から生成される1つ目の区間: [1,2]、 [1,2]を被覆する必要がある
スピーカー 2 から生成される2つ目の区間: [4,∞]、 [4,5]を被覆する必要がある
この問題は、制約 A から生成される各区間について動的計画法をすると解くことができます。
被覆しなければならない区間それぞれについて、(被覆するためにかかるコスト, 被覆した場合に余る右端の部分) を保持して、セグメント木などで管理することによって合計 $\mathrm{O}(Q log Q)$ で解くことができます。
バグを混入しやすい点
- $Q$ 秒後にはどのような音が鳴っていてもよいので、部分問題に分割するときに右端が∞となる区間ができる可能性があります。
- 部分問題に分解したあとの区間スケジューリング問題は、貪欲法で解くことは難しいです。セグメント木などを使って求める必要があります。