らくがき入門

機械学習を始めとしたコンピュータサイエンスを主に扱っています。

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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?