AtCoder Beginner Contest 089 D - Practical Skill Test - 思考のジャンプ幅が狭いなら，飛ぶ回数で補えばいいじゃない！！

f:id:hiro_kato:20190609190212p:plain

結論

要求されている処理・手順を全探索をベースとして愚直に書き出す．
実行制限時間を越えそうと判断したら，計算量の削減を考える．
データの持ち方や漸化式を用いることが有効な場合がある．

はじめに

AtCoderで出題された問題を復習しています．
公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います．

想定読者

解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

AtCoderのレートで緑下位．

記事の特徴

なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．
得られた前提知識や着眼点を言語化していきます．
間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．
- 連絡先：@k_hiro1818

問題のリンク

D - Practical Skill Test (400点)

発想・解法とそれらを引きだすための方法・解釈

最初の一歩は?
- 問題文で要求されている処理・手順を全探索をベースとして愚直に書き出す．
- 計算量の見積もりを行い，実行制限時間を越えそうと判断したら，計算量の削減を考える．
考察のキモ（Key Insight）は?
- STEP1: ある数が書かれた座標の位置を毎回調べるかわりに，データの持たせかたを工夫する．配列もしくはリストを使い，インデックスに「ある数」，インデックスに対応する値に「座標の位置」を格納する．
- STEP2: 一つのクエリを対象として，必要なコストを求めるときの計算量を減らす．
- STEP2-1: コストを計算するときに，移動の量が決まっていることを利用する．以下に示す形に分解して，漸化式を立てる．
  - 移動後のコスト=移動前のコスト+移動によるコスト
- STEP2-2: 累積和の考え方を利用して，コストを計算する．
- STEP3: $Q$ 個のクエリを計算する．
どうしたら思いつけそうか?
- STEP1: 視点を逆にする．グリッド全体を調べて対応する値を見つける⇒ある値に対応する座標を見つける．
- STEP2-1: 変わる部分と変わらない部分を整理する．変わらない部分に着目するとよさそう．コストの計算において，移動前後の状態に依存関係があるかどうかをみてみる．定式化できないか試す．
- STEP2-2: 分解してみる．条件を満たした集合の合計=全体の合計-条件を満たさない集合の合計．
実装のポイントは?

# STEP1：座標情報の格納にタプルを用いている．x座標，y座標それぞれ配列/リストを用意するケースも．

# STEP2-1：漸化式を更新する範囲．配列/リストのインデックス参照エラーにならないように，今回は1-index（要素数+1を用意）で処理．

# STEP3：Python3に限定されるが，改行コードとjoin(), map()を組み合わせて，1個ずつ出力．

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pieces = [0] * (h * w + 1)
    cost = [0 for _ in range(h * w + 1)]

    # STEP1：インデックスに「ある数」，インデックスに対応する値に「座標の位置」を格納
    for hi in range(h):
        for wi in range(w):
            number = a[hi][wi]
            pieces[number] = (hi, wi)

    # See:
    # https://img.atcoder.jp/abc089/editorial.pdf
    # https://www.youtube.com/watch?v=EDq1rl-6YcQ
    for i in range(d + 1, h * w + 1):
        prev_piece = pieces[i - d]
        next_piece = pieces[i]

        # STEP2-1: 漸化式．移動後のコスト=移動前のコスト+移動によるコストに分解
        cost[i] = cost[i - d] + \
            abs(next_piece[1] - prev_piece[1]) + \
            abs(next_piece[0] - prev_piece[0])

    # STEP3: Q個のクエリを計算
    q = int(input())
    ans = [0 for _ in range(q)]

    for j in range(q):
        lj, rj = map(int, input().split())

        # STEP2-2: 累積和の考え方を利用して，コストをO(1)で計算
        ans[j] = cost[rj] - cost[lj]

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()