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

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

CPSCO2019 Session1 C - Coins

AtCoder 有志コンテスト典型問題再帰組合せ全探索 300点問題

f:id:hiro_kato:20190504200054j:plain

目次

目次
はじめに
想定読者
記事の狙い
問題のリンク
ACに至るまでの考察・実装のコツなど
試行錯誤した過程
得られた知識・知見
感想
課題
参考

はじめに

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

想定読者

筆者と同じくらいのレートの方：失敗談・回り道をみて，共感していただける部分もあるかもしれません．
コンテストのwriterの方：サンプル $n=1$ ではありますが，レート茶色上位～緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません．

記事の狙い

丁寧でわかりやすい解説記事がたくさん公開されているため，解法そのものについての記述は少ないと思います．
ACに至るまでにどうしてそのような発想に至ったのか，考察や実装で試行錯誤した過程（=失敗談や回り道）を重視しています．
また，得られた前提知識や着眼点について，今後応用できるように抽象化・言語化していきます．
間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．
- 連絡先：@k_hiro1818

問題のリンク

C - Coins (300点)

ACに至るまでの考察・実装のコツなど

問われている内容

$N$ 個のうち $K$ 個を選ぶ組み合わせがある．
$K$ 個の商品の合計金額をちょうど支払うために最低限必要なコインの枚数を求める．

考えたこと

$N$ 個のうち $K$ 個を選ぶ組み合わせがある．
- 考えられるパターンをすべて列挙する．制約条件をみると，最大で32C6通り≒ $10 ^ 6$ 通り．
- 再帰を自分で実装するかPython3のライブラリ(itertools.combinations())を使う．
$K$ 個の商品の合計金額をちょうど支払うために最低限必要なコインの枚数を求める．
- 1つの処理を $O(1)$ もしくは $O(logN)$ としないとTLEしそう．
- 合計金額が $10 ^ x$ 円硬貨（ $x = 0～9$ ）をどれだけ使うかを数える．また， $10 ^ x$ 円硬貨が5枚以上あるときは， $5 * 10 ^ x$ 円硬貨（ $x = 0～9$ ）に置き換えると必要な枚数を減らせる．

実装（再帰Ver）

再帰が終了するケース（基本ケース）は $x = 0$ のとき．それまでの累計枚数と残りの金額を足した値が答え．
再帰ケースは $x >= 1$ のとき． $10 ^ 9$ 円硬貨で支払える枚数とあまった金額を求める． $5 * 10 ^ x$ 円硬貨（ $x = 0～9$ ）に置き換えられるかどうかを判定する．確定した枚数を，変数(ans)に足す．
$10 ^ 8$ 円硬貨で残りの金額を支払う．以降の処理は， $10 ^ 9$ 円硬貨と同様のため省略．
残りの硬貨についても同じように繰り返す．

提出コード

試行錯誤した過程

問題をみて，最初に思いだした過去問．
- DP（動的計画法）かと身構える．基礎中の基礎さえ理解が怪しいため．
再帰の実装に手間取ってしまった．
- 1円硬貨，5円硬貨を別々に考えていた．両方を組み合わせたときに最適となる場合があることに気がつくのに時間を要した（例えば，サンプル3）．
TLEだったら，最適となる組み合わせを $O(1)$ もしくは $O(logN)$ となるよう絞り込む必要がありそう．
- Python3で提出したらTLEとなった．ダメ元でPyPy3に変えて提出したところ通ってしまう．

得られた知識・知見

計算量の見積もり．
組み合わせを列挙，それぞれの場合についての処理を実行する．最大値や最小値を見つける．
再帰の基本ケースと再帰ケースを特定する．
ライブラリを使って得られた組み合わせをリストで返すとメモリの使用量が大きく増加．
実行時間の短縮のためにも，余分なループは回さない．

感想

これまで学んだ典型的な要素が組み合わさったいい問題だったと思います．
再帰の実装に手間取ってしまいましたが，コンテスト中にACできたところはよかったです．
PyPy3だと制限時間内に計算できるところがすごい．Python3で通している人もいました．

課題

再帰をスムーズに書けるように類題を解く．解説記事を読む．
組み合わせの列挙を再帰を使って実装できるようにする．
基礎的なDPを理解して解けるようにする．

参考

TODO: 公式解説がアップロードされたら追記
サムネイル画像

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