回答編集履歴
4
誤記および足りない記述を修正
answer
CHANGED
|
@@ -51,7 +51,7 @@
|
|
|
51
51
|
まず、単純に全部の組み合わせ数を求めると、`7 × 7 = 49` です。
|
|
52
52
|
|
|
53
53
|
|
|
54
|
-
問題の求めるところは奇数と偶数のペアですから、
|
|
54
|
+
問題の求めるところは奇数と偶数のペアですから、偶奇が同じぺアは除外します。ここで1/2 します。
|
|
55
55
|
|
|
56
56
|
|
|
57
57
|
各組み合わせにおいては`(1, 2)`と`(2, 1)`は同じですから、それらは除外します。つまり、ここで更に1/2します。
|
3
誤字脱字修正
answer
CHANGED
|
@@ -33,7 +33,7 @@
|
|
|
33
33
|
> k ** 2 >> 2でk以下の奇数の数 * 偶数の数を求められる訳が依然として分かりません。
|
|
34
34
|
> もしよろしければ、そちらについても解説していただけないでしょうか?
|
|
35
35
|
|
|
36
|
-
とコメントをいただいた
|
|
36
|
+
とコメントをいただいたので解法の意味するところまで考えていましたが、投稿直前に解決してしまいましたね。KSwordOfHasteさんの回答は私にとっても参考になったのですが、せっかく書いたので、考察のひとつとして追記しておきます。（間違いなどあればご指摘大歓迎です）
|
|
37
37
|
|
|
38
38
|
`k ** 2 >> 2` は、解法として `(k // 2) * ((k + 1) // 2)` とほぼ同じ意味合いを持っていると思います。冗長部分を削ぎ落としたショートカット(近道)と言って良いでしょうか。
|
|
39
39
|
|
|
@@ -59,6 +59,6 @@
|
|
|
59
59
|
|
|
60
60
|
1/2 を2回するわけで、1/4 、つまり 右2ビットシフト `>>` です。`k ** 2 >> 2` は この工程、(全組み合わせ数) ÷ 4 を表現したプログラミングと見ることができると思います。
|
|
61
61
|
|
|
62
|
-
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほどと思いました。実は私もこの
|
|
62
|
+
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほど、と思いました。実は私もこのAtCoder A問題を過去に解いたことがあったのでコードを見直してみたのですが、晒すには恥ずかしいほどに愚直な方法で解いていました。
|
|
63
63
|
|
|
64
|
-
以上、ご参考まで。
|
|
64
|
+
以上、ご参考までとなります。
|
2
解法にとっての考察を追記
answer
CHANGED
|
@@ -26,4 +26,39 @@
|
|
|
26
26
|
>>> print(k >> 4, bin(k >> 4))
|
|
27
27
|
0 0b0
|
|
28
28
|
>>>
|
|
29
|
-
```
|
|
29
|
+
```
|
|
30
|
+
---
|
|
31
|
+
**追記しました**：2019/04/21 10:18
|
|
32
|
+
|
|
33
|
+
> k ** 2 >> 2でk以下の奇数の数 * 偶数の数を求められる訳が依然として分かりません。
|
|
34
|
+
> もしよろしければ、そちらについても解説していただけないでしょうか?
|
|
35
|
+
|
|
36
|
+
とコメントをいただいたいので考えていましたが、投稿直前に解決してしまいましたね。KSwordOfHasteさんの回答は私にとっても参考になったのですが、せっかく書いたので、考察のひとつとして追記しておきます。（間違いなどあればご指摘大歓迎です）
|
|
37
|
+
|
|
38
|
+
`k ** 2 >> 2` は、解法として `(k // 2) * ((k + 1) // 2)` とほぼ同じ意味合いを持っていると思います。冗長部分を削ぎ落としたショートカット(近道)と言って良いでしょうか。
|
|
39
|
+
|
|
40
|
+
`k = 11`として、python3での`(k // 2) * ((k + 1) // 2)`式を一般の数式に当てはめてみます。(整数での演算なので、小数点以下は切り捨てられますが)
|
|
41
|
+
```
|
|
42
|
+
(11 ÷ 2) × ((11 ＋ 1) ÷ 2) = 5 × 6 = 30
|
|
43
|
+
```
|
|
44
|
+
|
|
45
|
+
これは、`11 × (11 ＋ 1) ÷ 2 ÷ 2` と変形できます。縮めれば `11 × 12 ÷ 4` です。答えは33になってしまいますが、考え方は同じように見えます。変形したために`(11 ÷ 2)`がなくなるので、小数部分が欠落せず、計算が合いませんがこれは仕方ありません。対して、`k ** 2 >> 2` を一般の数式に当てはめて見てみると `11 × 11 ÷ 4 ＝ 30` です。前述の式とほぼ同じです。
|
|
46
|
+
|
|
47
|
+
。。。納得行きませんか？ そうですね。私もなんか釈然としませんでした。発想を変えて、`k ** 2 >> 2` の式の意味するところを考えてみます。
|
|
48
|
+
|
|
49
|
+
ひとまず偶数奇数を考えず、kを二乗するのは、全組み合わせ数を求めるためのものとします。数が大きくなると面倒なので、`k = 7`とします。
|
|
50
|
+
|
|
51
|
+
まず、単純に全部の組み合わせ数を求めると、`7 × 7 = 49` です。
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
問題の求めるところは奇数と偶数のペアですから、それを除外します。ここで1/2 します。
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
各組み合わせにおいては`(1, 2)`と`(2, 1)`は同じですから、それらは除外します。つまり、ここで更に1/2します。
|
|
58
|
+
|
|
59
|
+
|
|
60
|
+
1/2 を2回するわけで、1/4 、つまり 右2ビットシフト `>>` です。`k ** 2 >> 2` は この工程、(全組み合わせ数) ÷ 4 を表現したプログラミングと見ることができると思います。
|
|
61
|
+
|
|
62
|
+
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほどと思いました。実は私もこのAtCocder A問題を過去に解いたことがあったのでコードを見直してみたのですが、晒すには恥ずかしいほどに愚直な方法で解いていました。
|
|
63
|
+
|
|
64
|
+
以上、ご参考まで。
|
1
表記を一部修正
answer
CHANGED
|
@@ -1,13 +1,12 @@
|
|
|
1
1
|
> ">>"で1/4になるのは分かるのですが、kが奇数のとき、k^2 / 4は小数となるはずなのに、
|
|
2
2
|
|
|
3
|
-
python3において
|
|
3
|
+
python3において `>>`などのビット演算は、整数を引数にとり、演算結果も整数です。
|
|
4
4
|
|
|
5
5
|
[Python3 - 6.8. シフト演算 (shifting operation)](https://docs.python.org/ja/3.5/reference/expressions.html?highlight=%E3%83%93%E3%83%83%E3%83%88#shifting-operations)
|
|
6
6
|
|
|
7
|
-
|
|
7
|
+
ビット演算ですので、2進数表記のビット単位で考えないと動きが分かりづらいと思います。2ビットシフトすると1/4になるのは結果的にそうなる場合があるというだけで、実際は右シフトするごとに最下位ビットは消えます。ですので奇数の場合でも 3 --> 1.5 --> 0.75 などとなるわけではありません。
|
|
8
8
|
|
|
9
|
-
|
|
9
|
+
下に、整数 7 を1ビットずつ右シフトする例を示してみます。
|
|
10
|
-
|
|
11
10
|
```bash
|
|
12
11
|
$ python3
|
|
13
12
|
Python 3.6.8 (default, Feb 15 2019, 01:54:23)
|