AtCoder精選良問「D - Snuke Panic (1D)」Diff 840

2023年4月19日 22:21

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

問題リンク

問題概要

数直線上に0,1,2,3,4と番号が振られた穴がある。
その５か所の穴のどこかから時刻Tに大きさAのすぬけが出てくる。
高橋くんは時刻１以内で穴を一つ移動できる。
適切に移動したときに最大となるすぬけの大きさを答える、という問題。

考え方

すぬけパニックというタイトルから、昔よく遊んだワニワニパニックを連想させる問題だ。
あまり覚えていないが、同時に色んな穴からワニが出てくることもあったと思う。その記憶があったため、今回も同時にすぬけが出てきたらやばいな、というように問題をミスリードしていた。

さて、今回のすぬけパニックは制約をよくみてみると、0<T1<T2<…<TN≤…となっているため、同時刻にすぬけが飛び出してくることはない。
そのため、ある時刻に捕まえられるすぬけは一匹で確定をする。

なんとなくDPっぽいなーと問題をみて考える。
というか、このDPっぽいなーというところに気づけるかどうかが問題を解けるか否かのポイントだと思う。

このDPっぽいと考える思考の流れは自分の中ではまだ整理できていないが、説明を試みる。

こういう時刻系の問題で最大とか最小という言葉が出てくると、自分はまず貪欲だとどうかなーというように考えてみる。

貪欲的に考えると、「一番でかいやつから捕まえるよう頑張ってみる」もしくは「とにかく手前から捕まえて頑張ってみる」みたいな感じになる。
ただ、少し考えるとそれは間違っているとわかる。
例えば前者であればこういうテストケースでは間違った答えになる。
時刻　穴　大きさの順

1 0 99
2 0 99
4 4 150

150を取ろうとして穴４に向かうよりも、動かないで0番の穴に待機していて、99 + 99と取る方が有利なケースだ。
後者の貪欲であればこうなる。

1 0 1
2 0 1
4 4 150

0番の穴に待機し続けるより、４番の穴に向かった方がいい。

このように時刻、穴、大きさのファクターが３つあると貪欲で解くのは難しい。

ではどうするかというと、もうDPしかない。うまく言えないのが歯がゆいが、DPしかないと言わざるを得ない。
DPにはそういうところがあると自分は半ばあきらめている。

とはいえ、もう少し言語化を試みてみる。
二次元のDPを使うとファクターを二つ使って残りの一つを最大化するような計算がとれる。つまり３つの要素を同時に考えることができる。

そういえば、有名なナップサック問題もそうだった。
重さの制限、重さ、価値という３つの要素があるから、DPを使って解く。

この問題で行くと最後に大きさを答えるので、DP[時刻][穴]=最大の大きさと言うように考える。

ある時刻にその穴にいるということは、一つ前の時刻からプラスマイナス１の穴から移動してきた、もしくは動かないでいた、の三通りある。
そのためDPの遷移式は以下のようになるだろう。

DP[時刻][穴] = MAX(DP[時刻-1][穴-1], DP[時刻-1][穴+1], DP[時刻][穴])

そして時刻、穴の組み合わせで運よくすぬけが出てくることがあれば、その大きさを足していく。

実装

DPテーブルはとても小さい数で初期化するようにする。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";


function main() {
    const n = nextNum()
    // 時刻Tにすぬけが出る穴とサイズ
    const holeSizeDic: Record<number, number[]> = {}
    // 最大の時刻
    let maxTime = 0
    for (let i = 0; i < n; i++) {
        const [t, x, a] = nextNums(3)
        maxTime = Math.max(t, maxTime)
        holeSizeDic[t] = [x, a]
    }
    // dp[i][j] 時刻iに穴jにいるときの捕まえた最大の大きさ
    const dp: number[][] = []
    const inf = -1 * (10 ** 18)
    for (let i = 0; i <= maxTime; i++) {
        const holes = new Array(5).fill(inf)
        dp.push(holes)
    }
    // 時刻0は0
    dp[0][0] = 0
    // 1秒目から繰り返す
    for (let i = 1; i <= maxTime; i++) {
        // 一個前の時間の各穴を見る
        for (let j = 0; j < 5; j++) {
            // 動かなかった場合
            dp[i][j] = dp[i - 1][j]
            // 左の穴から+1で移動してきて今の穴にいる場合
            if (j > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1])
            }
            // 右の穴から-1で移動してきて今の穴にいる場合
            if (j < 4) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1])
            }
        }
        // ここまでで今の時刻の各穴における最大が遷移されている
        // 運よく今の時刻にすぬけが出てくる穴があったら大きさを足す
        if (holeSizeDic[i]) {
            const [hole, size] = holeSizeDic[i]
            dp[i][hole] += size
        }
    }
    // 最後の時刻の最大値が答え
    let ans = 0
    for (let j = 0; j < 5; j++) {
        ans = Math.max(ans, dp[maxTime][j])
    }
    log(ans)
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}


// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}

少し違和感があるかもしれないのが、ここの箇所だろうか。


// ここまでで今の時刻の各穴における最大が遷移されている
// 運よく今の時刻にすぬけが出てくる穴があったら大きさを足す
if (holeSizeDic[i]) {
    const [hole, size] = holeSizeDic[i]
    dp[i][hole] += size
}

この記述だと例えば時刻１に穴４からすぬけが出てくる場合など、制約上、捕まえることが不可能なすぬけの大きさも足されることになる。
（穴４までの移動は時刻４が必要なため）

ただし、DPテーブルは-10**18と、とても小さい数で初期化されている。
そのため、有り得ない場面で多少のすぬけの大きさが足されても、答えに影響はない。言い方を変えれば０を超えることはない。

このあたりの遷移はDPテーブルをプリントしてみると良く分かる。

例えば以下のようなテストケースの場合。

※見栄えの都合上　-1000でDPテーブルを初期化した。

[
  [ 0, -1000, -1000, -1000, -1000 ],
  [ 0, 0, -1000, -1000, -900 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ]
]
------
[
  [ 0, -1000, -1000, -1000, -1000 ],
  [ 0, 0, -1000, -1000, -900 ],
  [ 0, 0, 0, -900, -900 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ]
]
------
[
  [ 0, -1000, -1000, -1000, -1000 ],
  [ 0, 0, -1000, -1000, -900 ],
  [ 0, 0, 0, -900, -900 ],
  [ 0, 0, 0, 10, -900 ],
  [ -1000, -1000, -1000, -1000, -1000 ],
  [ -1000, -1000, -1000, -1000, -1000 ]
]
------
[
  [ 0, -1000, -1000, -1000, -1000 ],
  [ 0, 0, -1000, -1000, -900 ],
  [ 0, 0, 0, -900, -900 ],
  [ 0, 0, 0, 10, -900 ],
  [ 0, 0, 10, 10, 10 ],
  [ -1000, -1000, -1000, -1000, -1000 ]
]
------
[
  [ 0, -1000, -1000, -1000, -1000 ],
  [ 0, 0, -1000, -1000, -900 ],
  [ 0, 0, 0, -900, -900 ],
  [ 0, 0, 0, 10, -900 ],
  [ 0, 0, 10, 10, 10 ],
  [ 0, 10, 10, 10, 11 ]
]
------

このように１秒目に100が足されて-900となっているが、答えには影響しない。この場合の答えは１１である。

この記事が気に入ったらサポートをしてみませんか？