CPSCO2019 Session1 C - Coins
目次
はじめに
AtCoderの問題を復習しています.
公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.
想定読者
筆者と同じくらいのレートの方:失敗談・回り道をみて,共感していただける部分もあるかもしれません.
コンテストのwriterの方:サンプル
ではありますが,レート茶色上位~緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません.
記事の狙い
丁寧でわかりやすい解説記事がたくさん公開されているため,解法そのものについての記述は少ないと思います.
ACに至るまでにどうしてそのような発想に至ったのか,考察や実装で試行錯誤した過程(=失敗談や回り道)を重視しています.
また,得られた前提知識や着眼点について,今後応用できるように抽象化・言語化していきます.
間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).
- 連絡先:@k_hiro1818
問題のリンク
ACに至るまでの考察・実装のコツなど
問われている内容
個のうち
個を選ぶ組み合わせがある.
個の商品の合計金額をちょうど支払うために最低限必要なコインの枚数を求める.
考えたこと
個のうち
個を選ぶ組み合わせがある.
考えられるパターンをすべて列挙する.制約条件をみると,最大で32C6通り≒
通り.
再帰を自分で実装するかPython3のライブラリ(itertools.combinations())を使う.
個の商品の合計金額をちょうど支払うために最低限必要なコインの枚数を求める.
1つの処理を
もしくは
としないとTLEしそう.
合計金額が
円硬貨(
)をどれだけ使うかを数える.また,
円硬貨が5枚以上あるときは,
円硬貨(
)に置き換えると必要な枚数を減らせる.
実装(再帰Ver)
再帰が終了するケース(基本ケース)は
のとき.それまでの累計枚数と残りの金額を足した値が答え.
再帰ケースは
のとき.
円硬貨で支払える枚数とあまった金額を求める.
円硬貨(
)に置き換えられるかどうかを判定する.確定した枚数を,変数(ans)に足す.
円硬貨で残りの金額を支払う.以降の処理は,
円硬貨と同様のため省略.
残りの硬貨についても同じように繰り返す.
試行錯誤した過程
問題をみて,最初に思いだした過去問.
- DP(動的計画法)かと身構える.基礎中の基礎さえ理解が怪しいため.
- DP(動的計画法)かと身構える.基礎中の基礎さえ理解が怪しいため.
再帰の実装に手間取ってしまった.
- 1円硬貨,5円硬貨を別々に考えていた.両方を組み合わせたときに最適となる場合があることに気がつくのに時間を要した(例えば,サンプル3).
- 1円硬貨,5円硬貨を別々に考えていた.両方を組み合わせたときに最適となる場合があることに気がつくのに時間を要した(例えば,サンプル3).
TLEだったら,最適となる組み合わせを
もしくは
となるよう絞り込む必要がありそう.
- Python3で提出したらTLEとなった.ダメ元でPyPy3に変えて提出したところ通ってしまう.
- Python3で提出したらTLEとなった.ダメ元でPyPy3に変えて提出したところ通ってしまう.
得られた知識・知見
計算量の見積もり.
組み合わせを列挙,それぞれの場合についての処理を実行する.最大値や最小値を見つける.
ライブラリを使って得られた組み合わせをリストで返すとメモリの使用量が大きく増加.
実行時間の短縮のためにも,余分なループは回さない.
感想
これまで学んだ典型的な要素が組み合わさったいい問題だったと思います.
再帰の実装に手間取ってしまいましたが,コンテスト中にACできたところはよかったです.
PyPy3だと制限時間内に計算できるところがすごい.Python3で通している人もいました.
課題
参考
TODO: 公式解説がアップロードされたら追記
記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.