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

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

AtCoder Beginner Contest 129 C - Typical Stairs

目次

結論

  • 次の状態が直前の状態に依存していると判断したら,動的計画法を解法の候補に入れる.

  • 動的計画法の基本は,「何を状態として持つか?」と「どんな遷移をするか?」.

  • シンプルな条件で,どうなるか実験してみる.その後,追加の条件がある場合を考える.

  • 数式(漸化式)で表現できないか試す.

はじめに

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

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

想定読者

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

筆者の実力

  • AtCoderのレートで緑下位

記事の特徴

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

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

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


問題のリンク

C - Typical Stairs (300点)

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

  • 最初の一歩は?

    • 次の状態が,直前の状態に依存していることを読み取る.
  • 考察のキモ(Key Insight)は?

    • 動的計画法を使う.

    • 「何を状態として持つか?」⇒ 移動方法の組み合わせの数.

    • 「どんな遷移をするか?」⇒ 1マスもしくは2マス進む≒あるマスに着目したときに,1マス前/2マス前の組み合わせの数の和をとる.

    • 通れないマスのときは,状態を更新しない.

  • どうしたら思いつけそうか?

    • 図を書いてみる.矢印の書き方≒遷移をそのまま表しているケースも.

    • 次の状態が,直前の状態に依存しているかどうかをチェックしてみる.

    • シンプルな条件(通れるマスだけの場合)で,どうなるか実験してみる.その後,追加の条件(通れないマス)がある場合を考える.

    • 数式(漸化式)で表現できないか試す.

    • 類題を解いて経験を積む.

  • 実装のポイントは?

    • 配列の参照外エラーを回避するため,dpの要素を n + 2個にする.ほかにも,提出されたAC解を拝見したところ,if文で場合分けしているケースがかなりありました.

Python3による回答例

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


def main():
    n, m = map(int, input().split())
    mod = 10 ** 9 + 7
    broken = [False for _ in range(n + 1)]
    dp = [0 for _ in range(n + 2)]
    dp[n] = 1

    for i in range(m):
        ai = int(input())
        broken[ai] = True

    # See:
    # https://www.youtube.com/watch?v=L8grWxBlIZ4
    for j in range(n - 1, -1, -1):
        if broken[j]:
            continue

        dp[j] = dp[j + 1] + dp[j + 2]
        dp[j] %= mod

    print(dp[0])


if __name__ == '__main__':
    main()

得られた知識・知見

  • 動的計画法の基本は,「何を状態として持つか?」と「どんな遷移をするか?」.

  • 最終的な状態から見る という視点.

感想

  • 愚直に書き出した結果,組み合わせの数がフィボナッチ数列だと気がつけたところは成長したと思います.

  • 通れないマスの処理がうまくできず,本番中にACできませんでした.連続して通れるマスの数に対応したフィボナッチ数列の値を返せばよいと思っていましたが,サンプル3が合わず…

課題

参考

drken1215.hatenablog.com

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

更新履歴

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