D - AtArcher Editorial
by 
square1001
本コンテストの問題 D「AtArcher」の解説です。
この問題で使われる的には、「中心に近いほど高得点が得られる」という性質があります。これを上手く使うことが、この問題を解くための鍵となります。
解説の目次
この問題の解法は 3 ステップに分かれています。
- ステップ 1：最適解の「パターン」を考える
- ステップ 2：全探索の問題に落とし込む
- ステップ 3：全探索の高速化①
- ステップ 4：全探索の高速化②
それ以降の解説では、5 節で解法のまとめ、6 節で実装例 (C++, Python) について書きます。なお、急いで解説を読みたい方は、5 節「解法のまとめ」を読んでください。
ステップ 1. 最適解の「パターン」を考える
この問題で使われる的には「中心に近いほど高得点が得られる」という性質があります。どのように打てば最適解が得られるのか、考えてみましょう。
まず、得点を上げるためには、矢を中心に “寄せる” ことが大切です。
上図（\(D = 3\) の例）では、矢を当てる位置を中心に寄せた結果、得点が上がっています。実際に、矢を中心に寄せることによって、それぞれの矢の得点が下がることはないので、全体の得点も下がることはありません。
矢をギリギリまで中心に寄せると、それぞれの座標は \(x, x+D, x+2D, \dots, x+(N-1)D\) と、等間隔な当たり方になります。上図は \(x = -5\) の例になっています。
これが「最適解のパターン」となり、これを上手く全探索することで問題を解く、といった方針につながります。これについては次節以降で述べます。
ステップ 2. 全探索の問題に落とし込む
まず、矢を中心に寄せることで、必ず \(-(N-1)D \leq x \leq 0\) を満たします。この理由は次の通りです：
- もし \(x \lt -(N-1)D\) であれば、右に寄せることでさらに中心に近づけられるから
- もし \(x \gt 0\) であれば、左に寄せることでさらに中心に近づけられるから
また、\(x\) は整数に限定してもよいです。なぜなら、\(x\) が整数でないとき、これを最も近い整数に変えても、得点は変わらないからです。
したがって、\(x = -(N-1)D, -(N-1)D+1, -(N-1)D+2, \dots, -1, 0\) の合計 \((N-1)D+1\) 通りの撃ち方を全探索すれば、この中で最も高い得点が答えになります。
1 つの \(x\) に対して合計得点を求めるのには、単純に実装すると計算量 \(O(NM)\) かかります。ここで、「各区間に入る矢が何本か」を割り算を使って求めることを考えます。実際に計算すると、座標が \(L\) 以上 \(R\) 未満の領域には
\[\max\left(\min\left(\left\lceil \frac{R-x}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L-x}{D} \right\rceil, N\right), 0\right)\]
本の矢が入ります。この理由は
- 座標 \(L\) 未満のエリアには、\(\max\left(\min\left(\left\lceil \frac{L-x}{D} \right\rceil, N\right), 0\right)\) 本の矢が入る
- 座標 \(R\) 未満のエリアには \(\max\left(\min\left(\left\lceil \frac{R-x}{D} \right\rceil, N\right), 0\right)\) 本の矢が入る
からです。これを \(2M-1\) 個の区間に対して計算すればいいので、1 つの \(x\) に対して \(O(M)\) で計算できるようになります。
したがって、全体計算量 \(O(NMD)\) でこの問題が解けます。しかし、\(N \leq 10^5, M \leq 10^5, D \leq 10^6\) の制約では 実行時間制限超過 (TLE) で不正解となります。
ステップ 3. 全探索の高速化①
先ほどは、\(x = -(N-1)D, -(N-1)D+1, -(N-1)D+2, \dots, -1, 0\) の場合を全探索していましたが、実はさらに探索を減らすことができます。
次の図を見てみましょう。確かに矢の位置は中心に寄せられていますが、直感的には最適解ではなさそうに見えます。
なぜ最適解ではないのでしょうか？
この理由は、座標 \(-11\) にある一番左の矢を一番右に移すことで、得点を上げることができるからです。具体的には、中心からの距離が \(11\) から \(4\) に近くなるから得点が上がり、それ以外の矢の位置は変わらないからです。
では、どのような場合に、一番左の矢を一番右に移したり、一番右の矢を一番左に移したりすることで、中心に近づけられるか考えてみましょう。
一番左の矢を一番右に移す場合
座標 \(x\) の矢を座標 \(x+ND\) に移すことを考えます。このとき、中心に近くなるのは \(-x \gt x+ND\) すなわち \(x \lt -\frac{ND}{2}\) のときです。
一番右の矢を一番左に移す場合 座標 \(x+(N-1)D\) の矢を座標 \(x-D\) に移すことを考えます。このとき、中心に近くなるのは \(x+(N-1)D \gt -(x-D)\) すなわち \(x \gt \frac{ND}{2}+D\) のときです。
したがって、これ以上中心に近づけられないような \(x\) の範囲は \(-\frac{ND}{2} \leq x \leq -\frac{ND}{2}+D\) となります。つまり、この範囲の \(x\) の中に必ず最適解があるといえます。
つまり、\(A = -\lfloor \frac{ND}{2} \rfloor\) として、\(x = A, A+1, A+2, \dots, A+(D-1)\) の合計 \(D\) 通りの撃ち方を全探索すれば、この中で最も高い得点が答えになります（\(x = A + D\) の場合も範囲に入るかもしれませんが、そのときは \(x = A\) の場合と対称な形になるので結果は同じです）。
先ほどの例で \((N-1)D+1 = 13\) 個の \(x\) に対して得点の計算を行う必要があったのが、\(D = 3\) 個に減らせているのが見て取れます。
したがって、この方法で全体計算量を \(O(MD)\) まで減らせました。しかし、それでも \(M \leq 10^5, D \leq 10^6\) の制約では 実行時間制限超過 (TLE) で不正解となります。
ステップ 4. 全探索の高速化②
さらに高速化するためにはどうすればよいのでしょうか。残念ながら、探索範囲をこれ以上狭めることはできません。ここで、\(x = A, A+1, A+2, \dots, A+(D-1)\) に対する合計得点を「一気に」計算したいです。
前の時点では、次のような方法で計算していました。
- \(x = A\) のときの合計得点を求める。つまり、\(x = A\) のときの \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) の合計を求める
- \(x = A+1\) のときの合計得点を求める。つまり、\(x = A+1\) のときの \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) の合計を求める
- （中略）
- \(x = A+(D-1)\) のときの合計得点を求める。つまり、\(x = A+(D-1)\) のときの \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) の合計を求める
ただし、\(L_i, R_i, S'_i\) は、的の左から \(i\) 番目の区間が座標 \(L_i\) 以上 \(R_i\) 未満で、得点 \(S'_i\) が得られることを意味します（ステップ 2 後半を参照）。具体的には、的の得点が入る区間は \(2M-1\) 個の区間に分けられ、次のようになります。
- \(L = (-x_M, -x_{M-1}, \dots, -x_2, -x_1, x_1+1, \dots, x_{M-2}+1, x_{M-1}+1)\)
- \(R = (-x_{M-1}, -x_{M-2}, \dots, -x_1, x_1+1, x_2+1, \dots, x_{M-1}+1, x_M+1)\)
- \(S' = (s_{M-1}, s_{M-2}, \dots, s_1, s_0, s_1, \dots, s_{M-2}, s_{M-1})\)
ここで、計算の角度を変えて、次の方法で計算することを考えてみましょう。
- 最初、\(x = A, A+1, \dots, A_{D-1}\) の合計得点 \(v_0, v_1, \dots, v_{D-1}\) をすべて \(0\) にセットする。
- 区間 \(1\) の貢献度を合計得点に加える。すなわち、\(k = 0, 1, 2, \dots, D-1\) に対して、\(v_k\) に \(\left\{\max\left(\min\left(\left\lceil \frac{R_1-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_1-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_1\) を加算する。
- 区間 \(2\) の貢献度を合計得点に加える。すなわち、\(k = 0, 1, 2, \dots, D-1\) に対して、\(v_k\) に \(\left\{\max\left(\min\left(\left\lceil \frac{R_2-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_2-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_2\) を加算する。
- （中略）
- 区間 \(2M-1\) の貢献度を合計得点に加える。すなわち、\(k = 0, 1, 2, \dots, D-1\) に対して、\(v_k\) に \(\left\{\max\left(\min\left(\left\lceil \frac{R_{2M-1}-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_{2M-1}-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_{2M-1}\) を加算する。
このように角度を変えて計算をするテクニックは、「貢献度を考えるテクニック」や「主客転倒」と呼ばれています。
足す値は複雑かもしれませんが、「区間 \(i\) に入る矢の本数」を表しています（ステップ 2 後半を参照）。この値が変化するのは、\(\left \lfloor \frac{L_i - (A+k)}{D} \right \rfloor\) の値が変わる時か、\(\left \lfloor \frac{R_i - (A+k)}{D} \right \rfloor\) の値が変わる時の、高々 2 回しかありません。だから、各ステップで足される \(v_0, v_1, v_2, \dots, v_{D-1}\) の値は \(a, a, \dots, a, b, b, \dots, b, c, c \dots, c\) のようになり、「高々 3 つの区間に同じ値を足す」という形になります。
区間に同じ値を足すことは、いもす法 を用いることによって高速に処理でき、最終的な \(v_0, v_1, \dots, v_{D-1}\) の値は \(O(M+D)\) で求まります。答えはそのうち最大の値になります。
5. 解法のまとめ
まとめると、この問題は次のようなステップで解くことができます。
- 矢を撃つ場所を『\(x, x+D, x+2D, \dots, x+(N-1)D\)』の形に限定しても、最適解が得られる
- さらに、\(A = -\left\lfloor \frac{ND}{2} \right\rfloor\) として、\(x = A, A+1, A+2, \dots, A+(D-1)\) の \(D\) 通りに限定しても、最適解が得られる
- 的の得点が入るゾーンは \(2M-1\) 個の区間に分かれるが、それぞれに対して「\(x = A, A+1, A+2, \dots, A+(D-1)\) の合計得点を加算する」操作をいもす法で行うことで、\(x = A, A+1, A+2, \dots, A+(D-1)\) それぞれの場合の得点が計算量 \(O(M+D)\) で求まる
- 答えは 3. で求まった中で最大の値となる
6. 実装例 (C++, Python)
C++ と Python の実装例を載せておきます。
posted:
last update: