【AtCoder】ABC 443 E - Climbing Silver

2026-02-06

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/動的計画法/Next DP 競技プログラミング

E - Climbing Silver

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

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1301 / NoviSteps: 1D / 配点: 450 点

問題概要

$N \times N$ のマス目があり、このマス目の上から $i$ 行目、左から $j$ 列目を $(i,j)$ と呼ぶ。マス目の情報は $N$ 個の文字列 $S_1,S_2,\dots,S_N$ として与えられ、 $S_i$ の $j$ 文字目が.のとき $(i,j)$ は空きマス、 #のとき $(i,j)$ は壁マスである。

はじめ、高橋君は空きマス $(N,C)$ におり、以下の移動を $N-1$ 回繰り返す。

現在高橋君が $(r,c)$ にいるとき、 $(r-1,c-1),(r-1,c),(r-1,c+1)$ のいずれかを移動先として指定する。但し、マス目中に存在しないマスを移動先として指定することはできない。
もし移動先 $(a,b)$ $(a, b)$ が壁マスである場合、以下のことが起こる。
- 現時点で $a < i \le N$ を満たす全ての整数について $(i,b)$ が空きマスであった場合、 $(a,b)$ にある壁を破壊し、移動する。
- そうでない場合、高橋君は移動に失敗する。この場合、移動が $N-1$ 回に満たなくとも直ちに移動の繰り返しを終了する。
もし移動先 $(a,b)$ が空きマスである場合、高橋君は $(a,b)$ に移動する。

以下の条件を満たす長さ $N$ の文字列 $R$ を出力せよ。

もし移動中に失敗せず $(1,i)$ に辿り着ける場合、 $R$ の $i$ 文字目は1
そうでない場合、 $R$ の $i$ 文字目は0

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

制約

$T,N,C$ は整数
$1 \le T \le 50000$
$2 \le N \le 3000$
$1 \le C \le N$
$S_N$ の $C$ 文字目は.
ひとつの入力について、 $N^2$ の総和は $9 \times 10^6$ を超えない

考察

まずは、移動先の壁を破壊できる条件を考えよう。

その壁が元々一番下の行にある場合 : 真下・斜め下のどちらから移動してきたとしても、その壁の下は全て空きマスなので、無条件に破壊できる。
その壁よりも下の行に壁が存在している(過去に存在していた) 場合 : 真下から移動してきた場合は、既に壁の下が全て空きマスであるはずだから、その壁を破壊できる。斜め下から移動してきた場合は、その壁の下に壁が存在している可能性があるため、その壁を破壊できない。

したがって、各列について、最も下に存在する壁の行番号を事前に記録しておくと良さそうである。

$L[j] :=$ $L [j] :=$ 列 $j$ $j$ における最も下に存在する壁の行番号(存在しない場合は $-1$ $- 1$ )
- 行 $i$ において $i > L[j]$ ならば、マス $(i, j)$ の下は全て空きマスであることが保証される。

この問題は一つ下の行の状態から現在の行の状態を決定できるので、動的計画法で解くことができる。定義は以下の通り。

$\mathrm{dp}_{i, j} :=$ $dp_{i, j} :=$ 高橋君がマス $(i, j)$ $(i, j)$ に到達した時点でのそのマスの状態
- $1$ : そのマスに到達可能で、かつ列 $j$ の行 $i+1$ から行 $N$ までが全て空きマスである
- $0$ : そのマスに到達可能で、かつ列 $j$ の行 $i+1$ から行 $N$ までに壁が存在する可能性がある
- $-1$ : そのマスに到達不可能である

初期条件は $\mathrm{dp}_{N, C} = 1, \quad \mathrm{dp}_{N, j} = -1 \ (j \neq C)$ である。

遷移は以下のようになる。

\mathrm{dp}_{i, j} = \underset{dj \in \{-1, 0, 1\}}{\max} \left( f((i+1, j+dj), (i, j)) \right)

ここで、マス $x = (i+1, j+dj)$ からマス $y = (i, j)$ への移動に対する $f(x, y)$ は、移動先のマス $y$ の状態によって以下のように定義される。

$y$ が空きマスの場合 :

f(x, y) = \begin{cases} 1 & (i > L[j]) \quad \text{(移動先に壁がない)} \\ \mathrm{dp}_{i+1, j} & (i \leq L[j] \land dj = 0) \quad \text{(マスの状態を引き継ぐ)} \\ -1 & (i \leq L[j] \land dj \neq 0) \quad \text{(壁が存在する可能性がある)} \end{cases}

$y$ が壁マスの場合 :

f(x, y) = \begin{cases} 1 & (i = L[j]) \quad \text{(その列の一番下の壁)} \\ 1 & (i < L[j] \land dj = 0 \land \mathrm{dp}_{i+1, j} = 1) \quad \text{(真下から移動し, かつ下が全て空きマス)} \\ 1 & (\mathrm{else}) \end{cases}

答えとしては、各列 $j$ について $\mathrm{dp}_{1, j} \neq -1$ ならば 1、そうでなければ 0 を出力すれば良い。

実装例

実装では、全体を 0-indexed で扱い、DPテーブルを1次元配列で管理している。

更新は俗に言う「Next DP」というやつ？

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 repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
6.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
7. 
8.template <typename T>
9.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
10. 
11.// ======================================== //
12. 
13.string solve()
14.{
15.    int N, C;
16.    cin >> N >> C;
17.    vector<string> S(N);
18.    rep(i, 0, N) cin >> S[i];
19. 
20.    vector<int> lowest_wall(N, -1);
21.    rep(j, 0, N) rrep(i, N - 1, 0)
22.    {
23.        if (S[i][j] == '#')
24.        {
25.            lowest_wall[j] = i;
26.            break;
27.        }
28.    }
29. 
30.    vector<int> dp(N, -1);
31.    dp[C - 1] = 1;
32. 
33.    rrep(i, N - 2, 0)
34.    {
35.        vector<int> next_dp(N, -1);
36.        bool is_reachable = false;
37. 
38.        rep(j, 0, N)
39.        {
40.            repe(dj, -1, 1)
41.            {
42.                int pj = j + dj;
43.                if (pj < 0 || pj >= N)
44.                    continue;
45. 
46.                if (dp[pj] == -1)
47.                    continue;
48. 
49.                int current_status = -1;
50. 
51.                if (S[i][j] == '.')
52.                {
53.                    if (i > lowest_wall[j])
54.                        current_status = 1;
55.                    else if (pj == j)
56.                        current_status = dp[j];
57.                    else
58.                        current_status = 0;
59.                }
60.                else
61.                {
62.                    if (i == lowest_wall[j])
63.                        current_status = 1;
64.                    else if (i < lowest_wall[j])
65.                    {
66.                        if (pj == j && dp[pj] == 1)
67.                            current_status = 1;
68.                        else
69.                            current_status = -1;
70.                    }
71.                }
72. 
73.                if (current_status != -1)
74.                {
75.                    chmax(next_dp[j], current_status);
76.                    is_reachable = true;
77.                }
78.            }
79.        }
80. 
81.        dp = next_dp;
82.        if (!is_reachable)
83.            break;
84.    }
85. 
86.    string ans;
87.    rep(j, 0, N) ans += (dp[j] == -1 ? '0' : '1');
88. 
89.    return ans;
90.}
91. 
92.int main()
93.{
94.    int T;
95.    cin >> T;
96. 
97.    while (T--)
98.    {
99.        cout << solve() << endl;
100.    }
101. 
102.    return 0;
103.}