A - Rhythm Game 解説
by 
square1001
今回のコンテストはいかがでしたでしょうか。過去 71 回の AtCoder Grand Contest の中で最も難しい問題セットだったと思いますが、楽しんでいただけたのであれば嬉しいです。それでは解説を始めていきたいと思います。
ステップ 1: スケジュールの問題に言い換える
競技プログラミングでは、問題のとらえ方を変えることで解法が見えやすくなることがあります。この問題は、以下の問題に言い換えることができます。
問題 \(N\) 個の課題がある。課題 \(i \ (1 \leq i \leq N)\) は \(T_i - X_i\) 秒後に出題され、連続する \(2 X_i\) 秒間で取り組む必要があり、締切は \(T_i + D + X_i\) 秒後である。今から課題をすべて終わらせることが可能か判定せよ。
ここでは、「座標 0 から出発してボタンを押して座標 0 に戻ってくる動作」を、課題に取り組む動作に言い換えています。みなさんも日常的に、学校の課題に取り組んだり、仕事のタスクをこなしていると思いますので、言い換えた問題の方が考えやすいかと思います。
ステップ 2: 終了時刻だけの問題を考える
いきなり問題の解法を考えるのは難しいので、まずは出題時刻を無視したバージョン（すべての課題が 0 秒後に出題される）を考えてみましょう。
この場合、締切の早い順に課題を行うのが最適になります。もしこの戦略で全部間に合ったら答えは Yes、間に合わなかったら答えは No になります。この戦略の最適性は、もし順番が逆転している箇所（連続する 2 つの課題）があっても締切に間に合うなら、逆転をほどいても締切に間に合う、という swap argument の考え方で証明できます。
厳密な証明
課題 \(i\) に取り組むのに \(c_i\) 秒かかり、締切が \(d_i\) 秒後であるとします。ここで、課題は締切順にソートされている、つまり \(d_1 \leq \dots \leq d_N\) とします。
仮に、課題 \(p_1, \dots, p_N\) の順にやって上手くいったとします。ここで、\(p = (1, 2, \dots, N)\) でない場合、\(p_i > p_{i+1}\) となる \(i\) が存在します。このとき、\(p_i\) と \(p_{i+1}\) の順番を入れ替えたスケジュールでも締切には間に合います。理由は以下の通りです。
ここで、\(p \neq (1, 2, \dots, N)\) の間、上の入れ替え操作を行い続けることを考えます。すると、\(p \neq (1, 2, \dots, N)\) の順番で締切に間に合った場合、\(p = (1, 2, \dots, N)\) の順番でも締切に間に合うことが分かります。したがって、締切の順番に課題に取り組むのが最適戦略になります。
ステップ 3: 開始時刻の制約があるとどうなるか？
ここでは課題が締切の順にソートされている、すなわち \(T_1 + X_1 \leq \dots \leq T_N + X_N\) を仮定します。
残念ながら、出題時刻の制約があると、ステップ 2 の議論は成立しません。理由は、逆転をほどく操作によって、出題時刻の制約を満たさなくなってしまう可能性があるからです。また、実際に、必ずしも締切の順にやるのが最適ではないケースがあります。
最適ではないケース
具体例として、\(N = 2\) で、課題 \(1\) は \(3\) から \(9\) 秒後までの間の連続する \(2\) 秒で、課題 \(2\) は \(0\) から \(10\) 秒後までの連続する \(6\) 秒で取り組むケースを考えます。残念ながら、課題 \(1\) から取り組むと、これが終わった時点で課題 \(2\) は時すでに遅し、となってしまいます。課題 \(2\) から取り組むと締切に間に合います。
このケースは、\(N = 2, D = 4, (T_1, X_1) = (4, 1), (T_2, X_2) = (3, 3)\) の場合に対応します。
それでは、swap argument の利用を本当に諦める必要があるのでしょうか？必ずしもそうではありません。逆転をほどいても出題時間の制約を満たす場合は、使うことができます。実はこの問題には、ちょうどよいところに以下の性質があります。
性質 2 つの課題 \(i_1, i_2 \ (i_1 < i_2)\) について、締切の遅い課題 \(i_2\) よりも後に締切の早い課題 \(i_1\) をやる場合、課題 \(i_1\) は直前の課題が終わってすぐに取り組むことができる（= この時点で既に出題されている）。
この性質は、課題のスケジュール決め問題の一般的なケースでは必ずしも成り立たないものの、本問題のケースでは成り立ちます。以下に証明を行います。
証明 課題 \(i_2\) は \(T_{i_2} - X_{i_2}\) 秒後に出題され、\(2X_{i_2}\) 秒かかるので、終わるのは早くとも \(T_{i_2} + X_{i_2}\) 秒後である。また、課題 \(i_1\) が出題されるのは \(T_{i_1} + X_{i_1}\) 秒後である。\(T_{i_1} + X_{i_1} \leq T_{i_2} + X_{i_2}\) であるため、課題 \(i_2\) が終わる時点で既に課題 \(i_1\) は出題されている。
この性質より、課題 \(i_1\) を前にずらす swap argument を適用することができます。理由は、課題 \(i_1\) を課題 \(i_2\) の後にやる限り、どんな順番でやっても課題 \(i_1\) はその出題時刻より後に取り組むことになるからです。その swap argument を適用すると、ある課題を終えた後により締切が早い課題が残っているとき、それらの課題を最優先に締切の早い順に行うのが最適 であることが分かります。
したがって、課題を行う順番は、上図の例で \((1), (2), (6, 3, 4, 5), (8, 7), (9), (10)\) と分けるように、「課題をひとつ選んでそれをやった後、残っているより番号の小さい課題を順にやる」というプロセスを繰り返す方法が最適であることが分かります。
ステップ 4: 動的計画法 (DP) で解く
ステップ 3 の考察より、この問題は動的計画法を使って解くことができます。
\(\mathrm{dp}[i]\) を「課題 \(1, 2, \dots, i\) が全部終わる時刻の最小値」（ただし不可能な場合は \(+\infty\)）とします。\(\mathrm{dp}[j]\) の状態から \(\mathrm{dp}[i]\) の状態に遷移する際に、課題 \(i, j+1, j+2, \dots, i-1\) を順にやることになります。この結果は、時刻 \(\mathrm{dp}[j]\) からシミュレーションして、締切に間に合うかどうか、間に合う場合は時刻いくつに終わるのか、を求める必要があります。このシミュレーションに計算量 \(O(N)\) かかることを踏まえると、全体計算量 \(O(N^3)\) で DP の値が全部求まります。答えは \(\mathrm{dp}[N] < \infty\) かどうかで判定できます。
以下の擬似コードのように計算することになります。
// 課題 i, j+1, j+2, ..., i-1 の順に行う動作をシミュレーションする関数
function simulate(j, i):
t := dp[j]
t := max(t, T[i]-X[i]) // i 番目の課題を始める
t := t + 2*X[i] // i 番目の課題に取り組む
if t > T[i]+D+X[i]
return INF
for k = j+1, ..., i-1 do
t := max(t, T[k]-X[k]) // k 番目の課題を始める
t := t + 2*X[k] // k 番目の課題に取り組む
if t > T[k]+D+X[k]
return INF
return t
// 動的計画法
dp = [0, INF, INF, ..., INF]
for j = 0, 1, ..., N-1 do
for i = j+1, j+2, ..., N do
res := simulate(j, i) // 遷移をシミュレーション
dp[i] := min(dp[i], res)
// 答えを出力
print (dp[N] != INF の場合 "Yes"、そうでない場合 "No")
ステップ 5: DP 高速化
この問題の制約は \(N \leq 5\,000\) なので、計算量 \(O(N^2)\) で解く必要があります。このために手っ取り早い方法は、ステップ 4 の DP を高速化することです。具体的に、\(\mathrm{dp}[j]\) の状態から \(\mathrm{dp}[i]\) の状態に遷移する際の結果を計算量 \(O(1)\) で求められるようにすることを考えます。
ここで使う性質は、課題 \(i, j+1, \dots, i-1\) の順にやるとき、課題 \(j+1, \dots, i-1\) は直前の課題が終わると同時に始められるということです。このため、ステップ 4 の擬似コードの 9 行目 t := max(t, T[k]-X[k]) は不必要です。すなわち、6 行目の時点での t の値を \(t_0\) とすると、特定の \(k\) のループが終わった時点での t の値は \(t_0 + 2X_{j+1} + \dots + 2X_k\) となります。よって、シミュレーション結果は以下のようになります。
- もし \(k = j+1, \dots, i-1\) のいずれかで \(t_0 + 2X_{j+1} + \dots + 2X_k > T_k + D + X_k\) となる場合、遷移できない（結果は \(+\infty\)）
- そうでない場合、最後の課題が時刻 \(t_0 + 2X_{j+1} + \dots + 2X_{i-1}\) に終わる
ここで、1. の条件は \(\max_{k = j+1, \dots, i-1} \{2X_{j+1} + \dots + 2X_k - (T_k + X_k)\} > D - t_0\) と書き換えられます。この max の値は、\(j\) を固定したときの（\(i\) に関する）累積 max なので、各 \((j, i)\) について計算量 \(O(1)\) で求めることができます。また、2. の結果も累積和を使って計算量 \(O(1)\) で求めることができます。よって、シミュレーション結果を計算量 \(O(1)\) で求めることができ、全体計算量 \(O(N^2)\) で DP の値が全部求まります。
解答例 (C++)
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
// 配列を指定した順序で並び替える関数
vector<long long> permute(int N, const vector<long long>& A, const vector<int>& perm) {
vector<long long> res(N);
for (int i = 0; i < N; i++) {
res[i] = A[perm[i]];
}
return res;
}
// 問題を解く関数（答えが Yes なら true を、No なら false を返す）
bool solve(int N, long long D, vector<long long> T, vector<long long> X) {
// step #1. T[i] + X[i] の小さい順に並び替え
vector<int> ranking(N);
for (int i = 0; i < N; i++) {
ranking[i] = i;
}
sort(ranking.begin(), ranking.end(), [&](const int a, const int b) {
return T[a] + X[a] < T[b] + X[b];
});
T = permute(N, T, ranking);
X = permute(N, X, ranking);
// step #2. 動的計画法
const long long INF = 7LL << 58;
vector<long long> dp(N + 1, INF);
dp[0] = 0;
for (int j = 0; j < N; j++) {
long long sum = 0; // X[j] + ... + X[i-1] を管理
long long current_max = -INF; // 2X[j] + ... + 2X[k-1] - (T[k]+X[k]) の累積 max を管理
for (int i = j + 1; i <= N; i++) {
long long t0 = max(dp[j], T[i - 1] - X[i - 1]) + 2 * X[i - 1];
if (t0 <= T[i - 1] + D + X[i - 1]) {
if (current_max <= D - t0) {
long long finish = t0 + sum * 2;
dp[i] = min(dp[i], finish);
}
}
sum += X[i - 1];
current_max = max(current_max, sum * 2 - (T[i - 1] + X[i - 1]));
}
}
// dp[N] < INF なら答えは Yes
return dp[N] < INF;
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int TESTCASES;
cin >> TESTCASES;
for (int id = 1; id <= TESTCASES; id++) {
int N; long long D;
cin >> N >> D;
vector<long long> T(N), X(N);
for (int i = 0; i < N; i++) {
cin >> T[i] >> X[i];
}
bool ans = solve(N, D, T, X);
cout << (ans ? "Yes" : "No") << '\n';
}
return 0;
}
投稿日時:
最終更新: