回答編集履歴
1
補足を追加
answer
CHANGED
|
@@ -4,4 +4,28 @@
|
|
|
4
4
|
- `b`の値を`a + 1`から「合計値`x`の二分の一より1小さな数」まで変化させつつ
|
|
5
5
|
- 計算(x - a - b)で求めた`c`の値が`b`より大きく、かつ`n`以下である
|
|
6
6
|
|
|
7
|
-
なら、合計が`x`になる組み合わせ`a, b, c`を一組見つけたことになるから。
|
|
7
|
+
なら、合計が`x`になる組み合わせ`a, b, c`を一組見つけたことになるから。
|
|
8
|
+
|
|
9
|
+
補足:
|
|
10
|
+
> 1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数
|
|
11
|
+
|
|
12
|
+
1からnまでの整数(問題文には明示されていないが、続く文章や例から確実)から3つの数を重複無く選ぶということは、
|
|
13
|
+
|
|
14
|
+
- 3つの整数はそれぞれ異なるので、大小関係が成り立つ
|
|
15
|
+
|
|
16
|
+
ということです。そこで、解法を提示しているブログでは、
|
|
17
|
+
|
|
18
|
+
- 3つの重複しない整数をそれぞれ`a`, `b`, `c`とする
|
|
19
|
+
- **便宜的に**、`a < b < c`の関係が成り立つとする
|
|
20
|
+
|
|
21
|
+
としています。つまり、3つの整数のうち、一番小さなものを`a`、二番目に小さなものを`b`、三番目に小さなものを`c`として扱います。
|
|
22
|
+
|
|
23
|
+
すると、`a`は「少なくとも合計値`x`の三分の一よりは小さい」ことが必要です。なぜなら、`a`と、それより大きな`b`や`c`との合計が`x`にならないといけないからです(重複を許せば、合計値`x`の三分の一が`a`の上限となります)。
|
|
24
|
+
|
|
25
|
+
`b`の値は、`a`の値より大きいことが必要で、なおかつ「合計値`x`から`a`の値を引いた数の二分の一より小さい」ことも必要です。なぜなら、`b`と、それより大きな`c`との合計が、「合計値`x`から`a`の値を引いた数」にならないといけないからです(重複を許せば、合計値`x`から`a`の値を引いた数の二分の一が`b`の上限となります)。
|
|
26
|
+
|
|
27
|
+
`c`の値は、「合計値`x`から`a`の値と`b`の値を引いた数」で求められますが、これは`b`より大きいことが必要で、なおかつ`n`以下である必要があります。
|
|
28
|
+
|
|
29
|
+
以上を効率よく探すために、`range`で整数の範囲を指定し、条件に当てはまるときに(初期値0の)`cnt`を1増やせば、最終的な組み合わせの数が得られます。
|
|
30
|
+
|
|
31
|
+
`cnt += 1`の直後の行に、同じだけインデント(字下げ)した`print(f"{a} {b} {c}")`を追加してみれば、見つかった組み合わせが表示されるので、理解が深まるでしょう。
|