Mister雑記

競プロやります。

ABC089-D「Practical Skill Test」(400)

問題リンク:D - Practical Skill Test


解説2問目。この問題は本番でアタックしていたが実力不足ゆえに時間切れとなってしまった、個人的に苦い思い出のある問題でもある。 今となっては確実に解けるようになったが、なかなかに奥が深い問題だと思う。

問題概要:

H*Wのマスに数字が1~H*Wまで1つづつ書かれている。 マス上には駒が1つ置かれている。 このとき、Q個のクエリが以下のように与えられるので、それぞれについて解答を出力せよ。

  • クエリは2つの自然数L, Rからなる。
  • 最初、駒がLと書かれたマス(以降「マスL」と表記する)に置かれている。
  • (i, j)にある駒を(x, y)へ移すのに魔力|x - i|+|y - j|を消費する。
  • ただし、駒がマスxにいるときには駒をマスx+Dにしか移動することができない。
  • このとき、駒をマスRへ移動させるのに必要な魔力を求める。
  • Dは全クエリについて共通な自然数であり、R>=LかつR-LがDの倍数であることが保証される。

これだけではよく分からないと思うので、具体的な例を以下に示す。

f:id:misteer:20180605131629j:plain


初めて読んだ人は「何言ってんだこいつ」となりそうな問題である。 しかしその手の問題に直面した場合、面倒がらずに上のように具体例を図で描くことは極めて重要である。

愚直解:

問題内容を理解してまず考えるべきは「愚直解」、つまり「実行時間は無視して、とりあえず問題は解ける」という解法である。 例外はあれど、最初からTLEの心配をするよりも「愚直解を考える」→「要らない計算を削って時間短縮」or「より効率的なアルゴリズムに置換」という方針の方が上手くいく場合が多いと個人的に考えている。

何はともあれ、まずは「やるべきこと」を整理する。
各クエリで必要な操作を羅列していくと、

  • Aの座標を求める
  • A+Dの座標を求める
  • 各座標から魔力を算出
  • A+D<Bなら、A=A+Dとして上を繰り返す
  • Bに着いたら魔力の総和を出力

といった具合になる。
そしてこれをそのまま実装すると以下のようになる。 

int main() {
    int H, W, D;
    cin >> H >> W >> D;

    int A[H][W];
    // 各マスの数値を記録
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> A[i][j];
        }
    }

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++) {
        // ここからクエリを捌いていく
        int L, R;
        cin >> L >> R;
        ll mp = 0;
        // 消費した魔力(Magic Point)

        while (L < R) {
            // LとL+Dを探す
            int x1, y1, x2, y2;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (A[i][j] == L) {
                        x1 = i;
                        y1 = j;
                    } else if (A[i][j] == L + D) {
                        x2 = i;
                        y2 = j;
                    }
                }
            }

            // 魔力を計算
            mp += abs(x2 - x1) + abs(y2 - y1);

            // 駒をすすめる
            L = L + D;
        }
        // Rに着いたら魔力を出力
        cout << mp << endl;
    }
    return 0;
}

これでも一応解けるが、無駄が多いのはなんとなく分かるだろう。 とりあえず計算量を見積もってみよう。

  • LとL+Dの位置を求めるのにO(H*W)
  • whileループはL=1、R=H*W、D=1のケースが最悪でこれはO(H*W)で抑えられる
  • クエリはQ回

ということでこのコードの計算量はO(Q*(H*W)^2)となる。 制約のH, W<=300、Q<=10^5からして明らかに間に合わない。
というわけで、ここから計算量を削っていく。

座標の記録方法:

上のコードでとりわけ目に付くのが、LとL+Dの座標を求める箇所である。 ここだけにO(H*W)の計算量を費やしているが、なんとかならないだろうか?


そこで一番最初の「マスの値の初期化」に注目する。上のコードではA[i][j]に座標(i, j)の値を入れることで初期化している。 これはある意味、「座標に値を入れている」と言える。 座標が与えられれば、そこの値をO(1)で取り出せるわけだ。
しかしこの問題、「数値から座標を求めたい」ことはあっても「座標から数値を求めたい」ことはない。 そこで、初期化するときに座標に数値を入れるんじゃなくて、数値に座標を入れることにする。そうすれば、マスの値からその座標がO(1)で求められるようになり、かなりの計算量を減らせるようになる。


というわけで、初期化の部分を以下のように書き換えてみる。

    pair<int, int> place[H*W+1];
    // 各数値の座標を記録
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int A;
            cin >> A;
            place[A] = {i, j};
        }
    }


ここでpairというデータ型を使っているが、要素が2つしかない配列だと思ってくれれば十分である。 pairに慣れていないようであれば、x[i]とy[i]という2つの配列を用意することで同等のことが実現できる。
そして、これによって座標を求める箇所は以下のように書き換えられる。

            while (L < R) {
            // LとL+Dを探す

            // 座標を求める
            int x1 = place[L].first;
            int y1 = place[L].second;
            int x2 = place[L + D].first;
            int y2 = place[L + D].second;

            // 魔力を計算
            mp += abs(x2 - x1) + abs(y2 - y1);

            // 駒をすすめる
            L = L + D;
        }

これで値から座標をO(1)で求められるようになり、計算量がO(Q*H*W)まで落ちた。

下ごしらえ:

しかし、これではまだTLEにハマってしまう(実際に試したら2/12ケースハマってしまった)。 クエリの数は削りようがないので、残すはwhileループをなんとかするしかない。 そこで、各クエリの計算量を減らすための「下ごしらえ」、つまり事前計算が必要となる。
さて、どういう事前計算をすれば計算量を落とせるか? 結論を言ってしまうと、「累積和DP」が有効である。前回 も解説したので軽く説明しておくと、「累積和」とはいくつか並んだ要素を途中まで全て足したもののことで、それをメモしていって再利用するというのが累積和DPである。 今回は累積和をメモしているので本当の意味で累積和DPと言える。

f:id:misteer:20180605125825p:plain
方針を説明したのが上の図。 このように、各マスについて「一番最初のマス」からそのマスまでの消費魔力をメモすれば、各クエリにO(1)で対処できる。 マスの移動ステップがDと全体で一定という制約がここで活きてきたわけだ。
この考え方は累積和の基本なので、自然に浮かぶようにしておきたいところである。

解答:

以上、解説が長くなったがこれらを実装したコードが以下の通り。

int main() {
    int H, W, D;
    cin >> H >> W >> D;

    pair<int, int> place[H * W + 1];
    // 各数値の座標を記録

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int A;
            cin >> A;
            place[A] = {i, j};
        }
    }

    int mp[H * W + 1];
    // 始点からの消費魔力をメモ

    // 下ごしらえ開始
    for (int i = 1; i <= H * W; i++) {
        if (i <= D) {
            // いわゆる「始点」なので消費魔力は0
            mp[i] = 0;

        } else {
            // 座標を求める
            int x1 = place[i - D].first;
            int y1 = place[i - D].second;
            int x2 = place[i].first;
            int y2 = place[i].second;

            // 魔力を計算
            mp[i] = mp[i - D] + abs(x2 - x1) + abs(y2 - y1);
        }
    }

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        // ここからクエリを捌いていく
        int L, R;
        cin >> L >> R;

        // 差分を取るだけで答えが出る
        cout << mp[R] - mp[L] << endl;
    }
    return 0;
}

このコードの計算量は事前計算にO(H*W)、クエリがQ回ということでO(H*W + Q)となり余裕で間に合う。 というわけで、これを提出すれば無事ACとなる。お疲れ様でした。

感想:

累積和で解けることにいかに早く気づけるかが鍵となりそうな問題。 400点としてはおそらく中位レベルと思われる。 水色になるなら時間内に解きたいレベルだろうか。(本当に?)
ところで解説用に一からコードを書き直したわけだが、 以前解いたときに出したコードより数段スッキリしたコードになった印象がある。 皆さんも綺麗なコードが書けなくて困っているなら、 最初から他人に解説するつもりで書くといいかもしれない。 そしてついでに解説してくださいおねがいします

余談:

上のコードを実際に走らせた結果のリンクをココに置いておく。 マクロは完全に省いたので幾分読みやすいと思われる。
https://beta.atcoder.jp/contests/abc089/submissions/2458097

そして前回同様、私が以前通したコードも置いておく。なぜか連想配列を使っているが、そこは気にしないで頂きたい。
https://beta.atcoder.jp/contests/abc089/submissions/2442786

あともしも解説して欲しい問題があれば、 ここのコメントで言っていただければ取り上げる可能性が非常に高くなります。よしなに。