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