回答編集履歴
4
誤記および足りない記述を修正
test
CHANGED
|
@@ -104,7 +104,7 @@
|
|
|
104
104
|
|
|
105
105
|
|
|
106
106
|
|
|
107
|
-
問題の求めるところは奇数と偶数のペアですから、
|
|
107
|
+
問題の求めるところは奇数と偶数のペアですから、偶奇が同じぺアは除外します。ここで1/2 します。
|
|
108
108
|
|
|
109
109
|
|
|
110
110
|
|
3
誤字脱字修正
test
CHANGED
|
@@ -68,7 +68,7 @@
|
|
|
68
68
|
|
|
69
69
|
|
|
70
70
|
|
|
71
|
-
とコメントをいただいた
|
|
71
|
+
とコメントをいただいたので解法の意味するところまで考えていましたが、投稿直前に解決してしまいましたね。KSwordOfHasteさんの回答は私にとっても参考になったのですが、せっかく書いたので、考察のひとつとして追記しておきます。（間違いなどあればご指摘大歓迎です）
|
|
72
72
|
|
|
73
73
|
|
|
74
74
|
|
|
@@ -120,8 +120,8 @@
|
|
|
120
120
|
|
|
121
121
|
|
|
122
122
|
|
|
123
|
-
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほどと思いました。実は私もこのAtCo
|
|
123
|
+
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほど、と思いました。実は私もこのAtCoder A問題を過去に解いたことがあったのでコードを見直してみたのですが、晒すには恥ずかしいほどに愚直な方法で解いていました。
|
|
124
124
|
|
|
125
125
|
|
|
126
126
|
|
|
127
|
-
以上、ご参考まで。
|
|
127
|
+
以上、ご参考までとなります。
|
2
解法にとっての考察を追記
test
CHANGED
|
@@ -55,3 +55,73 @@
|
|
|
55
55
|
>>>
|
|
56
56
|
|
|
57
57
|
```
|
|
58
|
+
|
|
59
|
+
---
|
|
60
|
+
|
|
61
|
+
**追記しました**：2019/04/21 10:18
|
|
62
|
+
|
|
63
|
+
|
|
64
|
+
|
|
65
|
+
> k ** 2 >> 2でk以下の奇数の数 * 偶数の数を求められる訳が依然として分かりません。
|
|
66
|
+
|
|
67
|
+
> もしよろしければ、そちらについても解説していただけないでしょうか?
|
|
68
|
+
|
|
69
|
+
|
|
70
|
+
|
|
71
|
+
とコメントをいただいたいので考えていましたが、投稿直前に解決してしまいましたね。KSwordOfHasteさんの回答は私にとっても参考になったのですが、せっかく書いたので、考察のひとつとして追記しておきます。（間違いなどあればご指摘大歓迎です）
|
|
72
|
+
|
|
73
|
+
|
|
74
|
+
|
|
75
|
+
`k ** 2 >> 2` は、解法として `(k // 2) * ((k + 1) // 2)` とほぼ同じ意味合いを持っていると思います。冗長部分を削ぎ落としたショートカット(近道)と言って良いでしょうか。
|
|
76
|
+
|
|
77
|
+
|
|
78
|
+
|
|
79
|
+
`k = 11`として、python3での`(k // 2) * ((k + 1) // 2)`式を一般の数式に当てはめてみます。(整数での演算なので、小数点以下は切り捨てられますが)
|
|
80
|
+
|
|
81
|
+
```
|
|
82
|
+
|
|
83
|
+
(11 ÷ 2) × ((11 ＋ 1) ÷ 2) = 5 × 6 = 30
|
|
84
|
+
|
|
85
|
+
```
|
|
86
|
+
|
|
87
|
+
|
|
88
|
+
|
|
89
|
+
これは、`11 × (11 ＋ 1) ÷ 2 ÷ 2` と変形できます。縮めれば `11 × 12 ÷ 4` です。答えは33になってしまいますが、考え方は同じように見えます。変形したために`(11 ÷ 2)`がなくなるので、小数部分が欠落せず、計算が合いませんがこれは仕方ありません。対して、`k ** 2 >> 2` を一般の数式に当てはめて見てみると `11 × 11 ÷ 4 ＝ 30` です。前述の式とほぼ同じです。
|
|
90
|
+
|
|
91
|
+
|
|
92
|
+
|
|
93
|
+
。。。納得行きませんか？ そうですね。私もなんか釈然としませんでした。発想を変えて、`k ** 2 >> 2` の式の意味するところを考えてみます。
|
|
94
|
+
|
|
95
|
+
|
|
96
|
+
|
|
97
|
+
ひとまず偶数奇数を考えず、kを二乗するのは、全組み合わせ数を求めるためのものとします。数が大きくなると面倒なので、`k = 7`とします。
|
|
98
|
+
|
|
99
|
+
|
|
100
|
+
|
|
101
|
+
まず、単純に全部の組み合わせ数を求めると、`7 × 7 = 49` です。
|
|
102
|
+
|
|
103
|
+
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
問題の求めるところは奇数と偶数のペアですから、それを除外します。ここで1/2 します。
|
|
108
|
+
|
|
109
|
+
|
|
110
|
+
|
|
111
|
+
|
|
112
|
+
|
|
113
|
+
各組み合わせにおいては`(1, 2)`と`(2, 1)`は同じですから、それらは除外します。つまり、ここで更に1/2します。
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
119
|
+
1/2 を2回するわけで、1/4 、つまり 右2ビットシフト `>>` です。`k ** 2 >> 2` は この工程、(全組み合わせ数) ÷ 4 を表現したプログラミングと見ることができると思います。
|
|
120
|
+
|
|
121
|
+
|
|
122
|
+
|
|
123
|
+
AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほどと思いました。実は私もこのAtCocder A問題を過去に解いたことがあったのでコードを見直してみたのですが、晒すには恥ずかしいほどに愚直な方法で解いていました。
|
|
124
|
+
|
|
125
|
+
|
|
126
|
+
|
|
127
|
+
以上、ご参考まで。
|
1
表記を一部修正
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
python3において
|
|
5
|
+
python3において `>>`などのビット演算は、整数を引数にとり、演算結果も整数です。
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
|
|
@@ -10,13 +10,11 @@
|
|
|
10
10
|
|
|
11
11
|
|
|
12
12
|
|
|
13
|
-
|
|
13
|
+
ビット演算ですので、2進数表記のビット単位で考えないと動きが分かりづらいと思います。2ビットシフトすると1/4になるのは結果的にそうなる場合があるというだけで、実際は右シフトするごとに最下位ビットは消えます。ですので奇数の場合でも 3 --> 1.5 --> 0.75 などとなるわけではありません。
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
|
|
17
|
+
下に、整数 7 を1ビットずつ右シフトする例を示してみます。
|
|
18
|
-
|
|
19
|
-
|
|
20
18
|
|
|
21
19
|
```bash
|
|
22
20
|
|