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

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

AtCoder Beginner Contest 068 D - Decrease (Contestant ver.)

目次

結論

  • 操作の終了後の状態から最初の状態に戻っていくことを試す.

  • シミュレーション回数が大きくなりそうなときは,周期性が見つからないか小さいサンプルで書き出してみる.

はじめに

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

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

想定読者

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

筆者の実力

記事の特徴

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

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

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


問題のリンク

D - Decrease (Contestant ver.) (600点)

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

  • 最初の一歩は?

    • 操作終了後から最初の状態へと戻っていく という視点.
  • 考察のキモ(Key Insight)は?

    • 上記の視点.視点を変えたことによる言い換え(ある要素を N増やす,それ以外の要素を1減らす).

    • 出力する配列を50個(上限)と決め打ち,0~49まで1つずつ要素を用意する.

    • 操作を繰り返すと周期性がある. Nの倍数ごとに,各要素が1ずつ増えている.

    •  Kが非常に大きい.愚直に K回シミュレーションする代わりに, K // Nだけ配列の各要素に加える. K% N回だけシミュレーションする.

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

    • 該当する答えの一つを出力するときは,最後の状態から最初の状態に戻っていくことを手がかりにする.

    • 周期性を見出すために, Nが小さい値を愚直に書き出してみる.

    • シミュレーション回数が大きくなりそうなときは,周期性と余りの関係を利用できないか考える.

Python3による回答例

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


def main():
    k = int(input())
    n = 50
    p, q = divmod(k, n)

    # 0~49の数字を用意
    # 規則性に基づいて,K // Nだけ加算
    a = [i + p for i in range(n)]

    # K % N回シミュレーション
    # ある要素だけ50増やす,残りはすべて1減らす
    # q回繰り返す
    for i in range(q):
        for j in range(n):
            if j == i:
                a[j] += 50
            else:
                a[j] -= 1

    print(n)
    print(' '.join(map(str, a)))


if __name__ == '__main__':
    main()

得られた知識・知見

  • 操作終了後から最初の状態に戻るという視点.

  • どこかを決め打ちできないか試す.

  • シミュレーション回数が大きくなりそうなときは,周期性と余りの関係を利用できないか考える.

感想

  • 実装に至るまでの考察のステップ数とそのステップ幅が,600点たるゆえんだと思いました(小並感).

参考

msatake.com

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

更新履歴

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