思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 089 D - Practical Skill Test

f:id:hiro_kato:20190609190212p:plain

目次

結論

  • 要求されている処理・手順を全探索をベースとして愚直に書き出す.

  • 実行制限時間を越えそうと判断したら,計算量の削減を考える.

  • データの持ち方や漸化式を用いることが有効な場合がある.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

  • AtCoderのレートで緑下位

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

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()

得られた知識・知見

  • 全探索を基準に考えて,計算量を見積もる.

  • 与えられるクエリが 10^{5}個の場合,各クエリを O(1)もしくは O(logN)で処理できるようにする.

  • 重複している処理を事前に計算して配列/リストに格納しておき,メインの処理では配列/リストにアクセスして利用する.

  • データ構造を工夫する.2次元配列/リストのデータを,座標と値を入れ替えて1次元配列/リストに変換できないか?

  • 前後の状態に依存関係がある場合,求めたい状態=直前の状態+更新条件と分解できないか?また,定式化できないか?

  • 着目点:変わらない部分はないか?

  • 条件を満たした集合=全体-条件を満たさない集合,を満たすとき累積和のような考え方が利用できないか?

感想

  • 計算量を大きく削減するために,データの持ち方や漸化式を用いるといった典型的な要素が含まれており,とても教育的な問題だと思いました.

  • 漸化式を立てるところが,自力でできるようになりたいです.求めたい状態が,直前の状態に依存していると気がつければよさそうだと思いました.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/09 作成
  • 2019/0x/xx 更新