[Boot camp for Beginners] B - Nice Shopping [Rust]

概要

AtCoder Problems: Boot camp for Beginners をRustで解いてみる

• 今回の問題：B - Nice Shopping
• 書いたコード：提出 #47311153 - 日立製作所 社会システム事業部 プログラミングコンテスト2020

学んだことmemo

• 組み合わせか...
  • 組み合わせを自分で全部かくの辛いな
  • AtCoderでよく使いそうなitertoolsのメソッド | makibishi throw
  • itertool というのが使えるらしい。
• 今回は長さの異なるiter二つを組み合わせるので、直積集合 というらしい
  • cartesian_product を使えば良さそう
• 添字の情報が消えないように、enumerate したiterの直積集合を作る
• 全ての組みに対して
  • クーポンがあるかどうかを探す
  • 複数あるパターンがあるので、findではなくfilter してmaxをとる
  • ai + bj - c して最終的な値段を出す
• という流れで回答できるかと思ったが、TLE(実行時間制限超過)になるパターンが多い
  • ダメだったパターン 提出 #47310625 - 日立製作所 社会システム事業部 プログラミングコンテスト2020

仕切り直し

• 全パターンの組み合わせを考える必要はなかった
• 最小になるパターン
  • クーポン使わないで最小同士の組
  • いずれかのクーポンを利用したもの
• どの組み合わせが最小か？ ではなく 最小の値段は なので組み合わせなんて見る必要がなかった
  • この辺りの思考の転換がまだ甘いので詰まる