Pythonで競プロに挑む日誌 vol.3-2 ~内包表記の練習~

超よく寝た.

現在の目標

• 完了: AtCoder をはじめる
• 今年の10月内に茶色を取得する ←イマココ
• 年内に緑色を取得する
• APG4b で C++ にも手を出す

本日の問題

昨日の Coins の続き

やったこと1: 力技をスマートに記述した
↓が昨日の回答.

before.py

# coding: utf-8
A, B, C, X = [int(input()) for i in range(4)]
#print(A, B, C, X)

# すべての和を出して、X と一致する個数を数える（力技）
cnt = 0
for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if (a * 500 + b * 100 + c * 50) == X:
                cnt += 1

print(cnt)

↓が今回の回答.

after.py

# coding: utf-8
A, B, C, X = [int(input()) for i in range(4)]


cnt = sum(a * 500 + b * 100 + c * 50 == X
          for a in range(A + 1)
          for b in range(B + 1)
          for c in range(C + 1))

print(cnt)

# 実行時間：51 ms
# メモリ　：2940 KB
# コード長：240 Byte
# 得点　　：200/200

内包表記を使うことでスマートになりました. 内包表記は, このような場面で威力を発揮するのですね.

---

やったこと2: 解き方を考え直した

answer1.py

# coding: utf-8
A, B, C, X = [int(input()) for i in range(4)]

cnt = 0
for a in range(A + 1):
    val_500 = X - 500 * a
    if val_500 >= 0:
        for b in range(B + 1):
            val_100 = val_500 - 100 * b
            if val_100 >= 0:
                if val_100 <= 50 * C:
                    cnt += 1
print(cnt)

# 実行時間：17 ms
# メモリ　：2940 KB
# コード長：332 Byte
# 得点　　：200/200

answer2.py

# coding: utf-8
A, B, C, X = [int(input()) for i in range(4)]

x = X // 50
cnt = 0
for a in range(A + 1):
    val1 = x - 10 * a
    if val1 >= 0:
        for b in range(B + 1):
            val2 = val1 - 2 * b
            if val2 >= 0:
                if val2 <= C:
                    cnt += 1
print(cnt)

# 実行時間：17 ms
# メモリ　：2940 KB
# コード長：319 Byte
# 得点　　：200/200

考え方

1. X から, 500 円玉を取り除く
2. 500 円玉を取り除いた X から, 100 円玉を取り除く
3. 500 円玉と 100 円玉を取り除いた X が, C 枚以内の 50 円玉でピッタリになるか判定する.
4. 500 円玉と 100 円玉の枚数を変えて, 1～3 を繰り返す.

コードは少し長くなりましたが, 実行速度は力技の 1/3 となりました. 他人のコードを読むと勉強になりますね.

answer1 はコインの金額から, answer2 はコインの枚数から計算しています. やっていることは実質同じですが, 枚数で計算したほうが少しだけコードが短くなりました.

明日やること

ABC083B - Some Sums を解く (今日やるかも).