Pythonで競プロに挑む日誌 vol.7 ~制約条件の利用と, sys.exit() による中断~

嵐は過ぎ去った.

現在の目標

• 今年の10月内に茶色を取得する ←イマココ
• 年内に緑色を取得する
• APG4b で C++ にも手を出す

今日の問題

ABC085C - Otoshidama
https://beta.atcoder.jp/contests/abs/tasks/abc085_c

結果

answer1.py

# coding: utf-8
N, Y = map(int, input().split())
ans = []
for i in range(N+1):
    for j in range(N+1 - i):
        k = N - (i + j)
        val = 10000 * i + 5000 * j + 1000 * k
        if val == Y:
            ans.append("{} {} {}".format(i, j, k))
            break

if ans == []:
    print("-1 -1 -1")
else:
    print(ans[0])

# 実行時間：832 ms
# メモリ　：3060 KB
# コード長：344 Byte
# 得点　　：300/300

問題文を素直にそのまま書き下したつもりなのですが... なんじゃこりゃ！めっちゃ遅い. なんでこんなに遅いのか...

少し粘ってみたのですが, あまり改善しなかったので他の方のコードを参照して書き直しました. その結果がコチラ↓

answer2.py

# coding utf-8
import sys
N, Y = map(int, input().split())

y = Y // 1000
diff = y - N
lim_a = y // 10
#ans = []
for a in range(lim_a + 1):
    b = (diff - 9 * a) // 4
    c = N - a - b
    val = (diff - 9 * a) % 4
    if b >= 0 and c >= 0 and val == 0:
        print(a, b, c, sep=" ")
        sys.exit()
        #ans.append("{} {} {}".format(a, b, c))

print("-1 -1 -1")
'''
if ans == []:
    print("-1 -1 -1")
else:
    print(ans[0])
'''

# 実行時間：18 ms
# メモリ　：3060 KB
# コード長：462 Byte
# 得点　　：300/300

今回は問題文から数式を立てて, パラメータをひとつ消して考えることが重要だったようです.

問題文の条件から2つ式を立てて, 1000 円札の枚数 c を消すと 10000　円札の枚数 a と, 5000円札の枚数 b に関する式が残ります. そして, 問題文から算出される範囲内で a が決まれば, b と c は芋づる式に求まります. 最後に b と c が 0 以上の整数であることを確認したらおしまいです.

for ループがひとつ減ったこと, sys.exit() を使って途中でむだな計算をさせないことで実行時間が短くなったのでしょうか.

感想
とても時間はかかったのですが, 「問題を正しく理解すること」, 「問題をうまいこと翻訳すること」の大切さを学べて楽しかったです. 結城浩さんの数学ガールシリーズには大事なことがたくさん書いてあったんだなぁ, と思いました.

明日やること

ABC049C - 白昼夢 / Daydream を解く.