問題
要約
-
2つの整数 K と S が与えられる。
-
3つの変数 X, Y, Z があり、それぞれ 0 以上 K 以下の整数値を取る。
-
X + Y + Z = S を満たす X, Y, Z の組み合わせの数を求める。
変数情報：
- K: 変数 X, Y, Z の取りうる最大値
- S: X, Y, Z の合計値
- X, Y, Z: 0 以上 K 以下の整数値を取る変数
この問題では、与えられた条件を満たす X, Y, Z の組み合わせの総数を求める必要があります。
既存投稿一覧ページへのリンク
アプローチ
全探索を用いて、条件を満たす組み合わせの数をカウントする。
ただし、効率的な探索を行うために、不要な探索を省略する最適化を行う。
このコードは、問題の条件を満たす組み合わせを効率的に全探索するために設計されている。
X, Y, Zの3つの変数があり、それぞれ0からKまでの値を取り得るため、単純な全探索では O(K^3) の計算量になる。
しかし、X + Y + Z = S という条件があるため、Zの値は X と Y が決まれば自動的に決定されます。そこで、X と Y の2重ループで探索し、Z の値を計算することで、計算量を O(K^2) に抑えています。さらに、X + Y > S となった時点で内側のループを終了することで、不要な計算を省いています。
解法手順
-
入力から K と S を受け取る。
-
カウンタ変数 count を 0 で初期化する。
-
変数 X の値を 0 から K まで順に探索する。
-
各 X に対して、Y の値を 0 から K まで順に探索する。
-
X + Y が S を超えた場合、それ以上 Y を増やしても条件を満たさないため、Y のループを終了する。
-
Z の値は S - (X + Y) で求められる。Z が 0 以上 K 以下であれば、条件を満たす組み合わせとしてカウントを 1 増やす。
-
すべての探索が終わったら、カウンタ変数 count の値を出力する。
ACコード
def io_func():
# 入力から K と S を受け取る
K, S = map(int, input().split())
return K, S
def solve(K, S):
# カウンタ変数 count を 0 で初期化する
count = 0
# 変数 X の値を 0 から K まで順に探索する
for X in range(K + 1):
# 各 X に対して、Y の値を 0 から K まで順に探索する
for Y in range(K + 1):
# X + Y が S を超えた場合、Y のループを終了する
if X + Y > S:
break
# Z の値を計算する
Z = S - (X + Y)
# Z が 0 以上 K 以下であれば、カウントを 1 増やす
if 0 <= Z <= K:
count += 1
# カウンタ変数 count の値を返す
return count
if __name__=="__main__":
# メイン処理
K, S = io_func()
result = solve(K, S)
print(result)
###
# 変数の意味:
# K: 整数の上限値
# S: X + Y + Z の合計値
# X, Y, Z: 0以上K以下の整数
# count: 条件を満たす組み合わせの数
# 1. io_func関数で標準入力から K と S を受け取る
# 2. solve関数で主な処理を行う
# - 2重ループを使用して X と Y の値を全探索する
# - 効率化のため、X + Y が S を超えた時点で内側のループを終了する
# - Z の値を S - (X + Y) で計算し、0以上K以下であればカウントを増やす
# 3. 最終的なカウント結果を出力する
計算量
このコードの計算量は O(K^2) 。
外側のループが K+1 回、内側のループが最大で K+1 回実行されるため。
X + Y > S となった時点で内側のループを終了する余地あり。