Pythonで競プロに挑む日誌 vol.19 ~制約条件を利用する練習~

現在の目標

• 2018年内に茶色になる←イマココ
• ABC の A, B 問題を全部解く
• 2018年度内に緑色を取得する
• 水色になったら, APG4b で C++ にも手を出す

今日のおはなし

結論

場合の数は大切.

解いた問題

B - Sum of Three Integers

for 文 2 つで時間かかった解答

answer1.py

# coding: utf-8
K, S = map(int, input().split())
cnt=0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0<=z<=K:
                cnt+=1
print(cnt)

# 実行時間 1490ms

解説 通りの方法で解けました. 解くには解けましたが, 時間がかかりました.

時短版解答

問題の制約条件を使えば, for ループを減らして数え上げるようです(ほかの方の解答を参照).

answer2.py

# coding: utf-8
K, S = map(int, input().split())
cnt=0
for x in range(K+1):
    yz = S - x
    if yz < 0:
            break
    elif yz > 2*K:
            continue
    else:
            cnt += yz + 1 - 2 * max(0, yz - K)
print(cnt)

# 実行時間 18ms

最後の一行が咀嚼できていないのですが, おそらく下記のようなアルゴリズムでしょうか.

• x を制約条件内 (0 から K までの K+1 個) で順番に調べる.
• ある x に対して, y + z が制約条件を満足しているか調べる.
  • 「y + z < 0 ならば, 以降の x に対して y + z < 0」なのでループ終了 (= カウント終了).
  • 「y + z > 2K」の場合, 制約を満足していないので次の x に更新する.
• y + z が制約条件を満たしている場合, ある x に対する y + z の場合の数の候補は (y + z + 1) 通り. そこから, 条件に合致しない場合の数を差っ引く?

むすび

制約条件を利用するには数学力がもっと必要. 間違ってたらご指摘ください.