【AtCoder】ABC 443 D - Pawn Line

2026-02-02

AtCoder/ABC/D問題 AtCoder/ABC/400点問題 AtCoder/茶Diff AtCoder/NoviSteps/1Q 競技プログラミング

D - Pawn Line

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 738 / NoviSteps: 1Q / 配点: 400 点

問題概要

$N \times N$ のマス目があり、各列に $1$ つずつ駒が置かれていて、 $i$ 列目の駒は上から $R_i$ 行目に置かれている。

あなたは以下の操作を $0$ 回以上何度でも行うことができる。

一番上の行以外に存在する駒をひとつ選び、その駒を上に隣接するマスに移動させる。

以下の条件を $1 \le i \le N-1$ を満たす全ての整数 $i$ について満たすようにするために必要な操作回数の最小値を求めよ。

$i$ 列目の駒が上から $x$ 行目、 $i+1$ 列目の駒が上から $y$ 行目に存在するとする。このとき、 $|x-y| \le 1$ を満たす。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めよ。

制約

入力は全て整数
$1 \le T \le 50000$
$2 \le N \le 3 \times 10^5$
$1 \le R_i \le N$
ひとつの入力について、 $N$ の総和は $3 \times 10^5$ を超えない

考察

列 $i$ にいる駒に注目すると、その一つ隣の列にいる駒は、最低でも上から $R_i + 1$ 行目まで移動させなければならない。

そのまた隣の列にいる駒は、最低でも上から $R_i + 2$ 行目まで移動させなければならない。

さらにその隣にいる駒は、最低でも上から $R_i + 3$ 行目まで移動させなければならない。

...

これを一般化すると、

列 $i$ から見て左右に $j$ 列離れた列にいる駒は、最低でも上から $R_i + |j - i|$ 行目まで移動させなければならない。

という条件が成り立つ。

この条件が全ての列 $(1 \leq j \leq N)$ に対して列 $i$ に係るので、最終的な各列の駒の行番号を $R_i^{\prime}$ とすると、

R_i^{\prime} = \underset{1 \leq j \leq N}{\min} (R_j + |j - i|) \tag{1}

となる。

この計算を全ての $i = 1, 2, \ldots, N$ について行うと $O(N^2)$ となり、 TLE となってしまう。

そこで、式 (1) の絶対値を以下のように分解しよう。

R_i^{\prime} = \min \left( \underset{1 \leq j \leq i}{\min} (R_j + i - j), \: \underset{i < j \leq N}{\min} (R_j + j - i) \right) \tag{2}

このとき、列 $i$ に対する左側からの制約 : $\underset{1 \leq j \leq i}{\min} (R_j + i - j) \iff \underset{1 \leq j \leq i}{\min} (R_j - j) + i$ に対して、累積minを取るDPの要領で、左端から右端に向かって

R_i^{\prime} \leftarrow \min(R_{i}^{\prime}, R_{i-1}^{\prime} + 1) \tag{3}

のように更新できる。

理由 (クリックで開く)

R_i^{\prime} = \min \left( \underset{1 \leq j \leq i}{\min} (R_j - j) + i \right)

について、両辺から $i$ を引くと、

R_i^{\prime} - i = \underset{1 \leq j \leq i}{\min} (R_j - j)

となる。この式は、 $R_j - j$ という数列の先頭から第 $i$ 項までの累積minを $R_i^{\prime} - i$ としていることを示す。

実際はこの漸化式をin-placeに計算できるので、

\begin{align*} R_i^{\prime} - i & \leftarrow \min(R_{i-1}^{\prime} - (i-1)) \\ \iff R_i^{\prime} & \leftarrow \min(R_{i-1}^{\prime} + 1) \end{align*}

と更新できることが分かる。

残る右側の制約も同様に、右端から左端に向かって

R_i^{\prime} \leftarrow \min(R_{i}^{\prime}, R_{i+1}^{\prime} + 1)

と更新できるので、 $R_i^{\prime}$ の計算は $O(N)$ 時間で可能となる。

あとは、 $\sum_{i=1}^{N} (R_i - R_i^{\prime})$ を計算して答えとして出力すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
6. 
7.using ll = long long;
8. 
9.template <typename T>
10.inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
11. 
12.// ======================================== //
13. 
14.ll solve()
15.{
16.    int N;
17.    cin >> N;
18.    vector<ll> R(N);
19.    rep(i, 0, N) cin >> R[i];
20. 
21.    vector<ll> target = R;
22.    rep(i, 1, N) chmin(target[i], target[i - 1] + 1);
23.    rrep(i, N - 2, 0) chmin(target[i], target[i + 1] + 1);
24. 
25.    ll ans = 0;
26.    rep(i, 0, N) ans += R[i] - target[i];
27. 
28.    return ans;
29.}
30. 
31.int main()
32.{
33.    int T;
34.    cin >> T;
35. 
36.    while (T--)
37.    {
38.        cout << solve() << endl;
39.    }
40. 
41.    return 0;
42.}