python 組み合わせの数

Question

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    cnt = 0

    for a in range(1, x // 3):
        for b in range(a + 1, x // 2):
            c = x - a - b
            if b < c <= n:
                cnt += 1

    print(cnt)

上のコードはAIZU ONLINE JUDGEの問題の解法をググって出てきたコードです。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/7/ITP1_7_B　←問題

組み合わせの数

1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。

例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、

1 + 3 + 5 = 9
2 + 3 + 4 = 9
の２通りがあります。

Input
複数のデータセットが入力として与えられます。各データセットでは、空白で区切られた n、x が 1 行に与えられます。

n、x がともに 0 のとき入力の終わりとします。

Constraints
3 ≤ n ≤ 100
0 ≤ x ≤ 300

Output
各データセットについて、組み合わせの数を１行に出力して下さい。

https://pontz-rw.hatenablog.jp/entry/2017/07/30/000000　←解法がのっていたブログ

とてもコンパクトにまとまっていて凄いと思うのですが、なぜ「b < c <= n」が成り立つときcntをインクリメントするのかがわかりません。ブログにコメントで伺おうと思ったのですが、コメント機能が使えませんでした。
ぜひ、教えていただけれると助かります。
よろしくお願いいたします。

Comments

[hentaiman]

> コメント機能が使えませんでした。
ログインしろと出ますね　アカウント作れば出来るかもしれませんね？

[hogeee]

ありがとうございます！そうだったんですね！アカウントを作りログインして、コメントにて質問しました。

Answer 1

ポイントは、3つの数が、aが一番小さい数、bがその次,cが一番大きな数としているところです。
そして、a,bを変化させならがcを求めてnまでに入っているかをチェックしてます。

a,bを決めると、c=x-a-bとcが決まります。
cがbより大きくn以下で範囲であれば成立ですね。

aはいちばん少ない数値ですから、残りb,cを足し合わせると少なくとも3倍上になるので
xの1/3以下までのチェックで十分です。
bも少なくとbより大きいcを足すと2倍になるので、xの1/2以下までのチェックで十分

別にaを1からxまでチェックしてbをa+1からxまでチェックしてもいいですが、上記の理由からaなら1/3を超えた部分には成立するものはないです。

Comments

[tmp]

すでに書いてあった。ローカルで書いて書き込み前に更新した方がいいですね

[hogeee]

いやー、せっかく書いていただいたのに申し訳ない。でも、ありがとうございます。

Answer 2

なぜ「b < c <= n」が成り立つときcntをインクリメントするのかがわかりません。

• aの値を1から「合計値xの三分の一より1小さな数」まで変化させつつ
• bの値をa + 1から「合計値xの二分の一より1小さな数」まで変化させつつ
• 計算(x - a - b)で求めたcの値がbより大きく、かつn以下である

なら、合計がxになる組み合わせa, b, cを一組見つけたことになるから。

補足:

1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数

1からnまでの整数(問題文には明示されていないが、続く文章や例から確実)から3つの数を重複無く選ぶということは、

• 3つの整数はそれぞれ異なるので、大小関係が成り立つ

ということです。そこで、解法を提示しているブログでは、

• 3つの重複しない整数をそれぞれa, b, cとする
• 便宜的に、a < b < cの関係が成り立つとする

としています。つまり、3つの整数のうち、一番小さなものをa、二番目に小さなものをb、三番目に小さなものをcとして扱います。

すると、aは「少なくとも合計値xの三分の一よりは小さい」ことが必要です。なぜなら、aと、それより大きなbやcとの合計がxにならないといけないからです(重複を許せば、合計値xの三分の一がaの上限となります)。

bの値は、aの値より大きいことが必要で、なおかつ「合計値xからaの値を引いた数の二分の一より小さい」ことも必要です。なぜなら、bと、それより大きなcとの合計が、「合計値xからaの値を引いた数」にならないといけないからです(重複を許せば、合計値xからaの値を引いた数の二分の一がbの上限となります)。

cの値は、「合計値xからaの値とbの値を引いた数」で求められますが、これはbより大きいことが必要で、なおかつn以下である必要があります。

以上を効率よく探すために、rangeで整数の範囲を指定し、条件に当てはまるときに(初期値0の)cntを1増やせば、最終的な組み合わせの数が得られます。

cnt += 1の直後の行に、同じだけインデント(字下げ)したprint(f"{a} {b} {c}")を追加してみれば、見つかった組み合わせが表示されるので、理解が深まるでしょう。

Comments

[hogeee]

なぜ見つけたことになるのでしょうか。そこがわからないポイントです。

[Daregada]

そういうときは、a, b, cではなく、実際の数で「紙に書く」とか「頭の中で想像する」とかして、具体的な動きを追って下さい。
それができないなら、デバッグ環境でステップ実行して、a, b, cの変化を追ってください。

[hogeee]

デバッグで追ったのですがわかりませんでした。
私が質問しているのは、「○○だからaの値をxの三分の1した数にすればいいんだな」「○○だからb < c <= nが成り立つときcntを増加させればいいんだな」という結論に至った過程がわかりません。

[hogeee]

素晴らしい解説ありがとうございます！ようやく謎が解けました。