ABC266 D問題 Snuke Panic 1D【C++, python】

At Coder

ABC266のD問題 Snuke Panic 1Dを解説します。

ポイント: DPテーブルをうまくつくる
DPとはDynamic Programmingの略です。日本語では動的計画法と呼ばれています。
DPの説明はここで行いません。
（というよりうまく解説ができません。。他の方の解説を見るようにしてください。）

ここではDPをある程度理解したという前提で、今回の問題ではどのようなDPテーブルをつくれば良いのか？を解説します。

結論としては、dp[i]][j]を以下のように定義し、2次元配列を作成したら良さそうです。

dp[i][j] = \( i \) 秒後に位置 \( j \) にいる時の最大値

実装の流れ
\( i \) 行目 \( j \) 列は、左上と真上と右上の最大値をとります。
（左上は \( i-1 \) 行 \( j-1 \) 列）
（真上は \( i-1 \) 行 \( j \) 列）
（右上は \( i-1 \) 行 \( j+1 \) 列）

その後、すぬけ君を捕まえられるのであればポイントを追加します。
（すぬけ君が出てこない場合もあるので、そのときは3つの最大値を取るだけです。）

下の図のようなイメージです。

どの \( i \) 行 \( j \) 列でも3つの最大値を取っています。
ただし、\( j = 0 \) の時、は左上が存在しないので、真上と右上の最大値を取るようにします。
\( j = 4 \) の時も同様に左上と真上の最大値を取るようにします。

入力例

3
1 0 100
3 3 10
5 4 1

C++での回答例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    map<int, int> x_mp, a_mp;
    
    int t_max = 0;      // 最後に出てくるすぬけ君の時間を管理
    rep(i, n) {
        int t, x, a;
        cin >> t >> x >> a;
        t_max = max(t_max, t);
        x_mp[t] = x;    // 時間をkeyとしてすぬけ君が出てくる位置を管理
        a_mp[t] = a;    // 時間をkeyとして出てきたすぬけ君の大きさを管理
    }
    // 入力の受け取り、ここまで

    vector<vector<long long>> dp(100005, vector(5)); // 2次元配列dpの準備
    rep(i, 5) {
        if (i == 0) dp[0][i] = 0;   // dp[0][0]には0を代入
        else dp[0][i] = -10;        // 高橋君が時間的に移動できない場所は-10とした
    }                               // （1秒後に位置3にいる等）

    for (int i = 1; i <= 100000; i++) { // iは時間
        rep(j, 5) { // jは高橋君の位置
            if (j == 0) { // 0に移動する時は1つ前にいた0か1のポイントが影響
                dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]);
            } else if (j == 4) { // 4に移動するには1つ前にいた3か4のポイントが影響
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]);
            } else { // 1,2,3に移動する時
                dp[i][j] = max(max(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]);

            } // 移動終了後に、すぬけ君を捕まえられるかのチェック
            if (x_mp[i] == j && dp[i][j] >= 0) {    // i秒経過時にjからすぬけ君がでてくる かつ 高橋君が時間的に移動できる場所である
                dp[i][j] += a_mp[i];                // 捕まえたすぬけ君の大きさを追加
            }
        }
    }

    long long ans = 0;
    rep(j, 5) {
        ans = max(ans, dp[t_max][j]);   // 最後のすぬけ君が出てきた時間の位置0, 1, 2, 3, 4のうち最大値をansとする
    }
    cout << ans << endl;
    return 0;
}

pythonでの回答例

n = int(input())

x_list = [0] * 100001
a_list = [0] * 100001
max_t = 0   # 最後に出てくるすぬけ君の時間を管理
for _ in range(n):
    t, x, a = map(int, input().split())
    max_t = max(max_t, t)
    x_list[t] = x   # 時間をkeyとしてすぬけ君が出てくる位置を管理
    a_list[t] = a   # 時間をkeyとして出てきたすぬけ君の大きさを管理
# 入力の受け取りここまで

dp = [[0] * 5 for _ in range(100001)]   # 2次元配列dpの準備
for j in range(1, 5):
    dp[0][j]  = -10 # 高橋君が時間的に移動できない場所は-10とした
                    # (1秒後に位置3にいる等)

for i in range(1, 100001):  # iは時間
    for j in range(5):      # jは高橋くんの位置
        if j == 0:          # 0に移動する時は1つ前にいた0か1のポイントが影響
            dp[i][j] = max(dp[i-1][j], dp[i-1][j+1])
        elif j == 4:        # 4に移動するには1つ前にいた3か4のポイントが影響
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])
        else:               # 1,2,3に移動する時
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])

        # 移動終了後に、すぬけ君を捕まえれるかのチェック
        if dp[i][j] >= 0 and x_list[i] == j:    # 高橋くんが時間的に移動できる位置 かつ i秒経過時にjからすぬけ君がでてくる
            dp[i][j] += a_list[i]               # 捕まえたすぬけ君の大きさを追加

ans = 0
for j in range(5):
    ans = max(ans, dp[max_t][j])    # 最後のすぬけ君が出てきた時間の位置0, 1, 2, 3, 4のうち最大値をansとする

print(ans)

コメント