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

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

AtCoder Typical DP Contest A - コンテスト

AtCoder 典型問題 動的計画法 組合せ 数え上げ

目次

結論

  • 直前の状態として，重複を除いた組み合わせの数を持つ．

  • 新しい要素に対して，直前の要素との合計を取り，重複した値があれば取り除く．

  • 重複を取り除くときにPython3ならset()を使うといい場合もある．

はじめに

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

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

想定読者

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

筆者の実力

記事の特徴

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

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

  • 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．


問題のリンク

A - コンテスト (2点)

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

この問題の難しいところ

  • N個の要素を選択する/選択しないの2択で考えると， 2^{100}≒10^{30}通りとなり実行時間制限に間に合わない．

考察のキモ（Key Insight）は?

  • i - 1個の要素を使ったときに得られる，得点の種類を状態として持つ．

  • i個目の要素を使い，上記の要素それぞれに足し算する．

  • 重複した要素を除外するため，集合を使う．

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

  • 直前の状態をうまく利用できないか?

  • その状態を表すものとして，何がよさそうか?

  • 制約条件が小さいものはないか?

実装のポイントは?

  • Pythonの場合は，集合を表すsetを使って重複した要素を弾いている．

  • set()に追加するときの計算量が気になるところ．dictと似ているという記述から判断すると，平均，最悪の場合ともに O(N)．

  • 今回の制約条件だと O(N^{3})だと思います（ここの部分が確信がなく，ご指摘いただけると幸いです）．

参考資料

wiki.python.org

PythonによるAC解の一例

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


def main():
    n = int(input())
    p = list(map(int, input().split()))
    ans = set()
    ans.add(0)

    for pi in p:
        candidates = list()

        for a in ans:
            candidates.append(a + pi)

        for candidate in candidates:
            ans.add(candidate)

    print(len(ans))


if __name__ == '__main__':
    main()

得られた知識・知見

  • 制約が小さければ，set()を使って重複を削除するという手段もある．

感想

  • 制約が小さいのをいいことに，set()を使って通した問題でした．実行時間制限を超えるかもしれないとヒヤヒヤしていました．計算量を正確に見積もれるようになるのと，動的計画法の基礎を学んでいきたいと思えたいい問題だったと思います．

参考

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

更新履歴

  • 2019/07/03 作成
  • 2019/0x/xx 更新