atcoder ABC123 B問題"Five Dishes"解法
ABC123のB問題、"Five Dishes"のPythonでの解法を記載します。
方針
10の倍数でしか注文ができないという制約があるので、下1桁が1が最大の注文ロスになることがわかります。 また、最大の注文ロスとなる料理以外は基本的に順番は問わないと考えられるため、単純に余りで降順にソートして、 料理作成の時間と10で割ったときの余りを足していくと全ての料理が届くまでの最小時間になるといえます。
- 余りでの降順ソートだが、10の倍数の数字は余りが0になってしまうため、10で置換し対応
- 元の調理時間と余りをペアにして、余りに基づいて降順にソート
実装上の工夫
- リスト内包表記内でif文を用いて0を10に置換
- 多重リストでのある特定のカラムでのソート
実装例
以下のコードでACです。
A = [int(input()) for i in range(5)] mod_list = [a % 10 for a in A] mod_list = [10 if a == 0 else a for a in mod_list] comb_list = [[a, b] for a, b in zip(A, mod_list)] sort_list = sorted(comb_list, key=lambda x: -x[1]) res = 0 for i, a in enumerate(sort_list): if i < 4: res += a[0] + (10-a[1]) else: res += a[0] print(res)
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る