回答編集履歴
4
追記
test
CHANGED
@@ -42,4 +42,4 @@
|
|
42
42
|
|
43
43
|
|
44
44
|
|
45
|
-
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか? は検討していません。
|
45
|
+
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか? は検討していません。宿題とします(私の)。
|
3
変更
test
CHANGED
@@ -28,7 +28,7 @@
|
|
28
28
|
|
29
29
|
|
30
30
|
|
31
|
-
場合の数的に考えると、1度のクエリで2増える
|
31
|
+
場合の数的に考えると、1度のクエリで2増えるor2減る、0なのでどちらか反転させてもう一度投げてみる*2のどちらかなので、それぞれ
|
32
32
|
|
33
33
|
|
34
34
|
|
2
追記
test
CHANGED
@@ -24,7 +24,21 @@
|
|
24
24
|
|
25
25
|
|
26
26
|
|
27
|
-
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな
|
27
|
+
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな。
|
28
|
+
|
29
|
+
|
30
|
+
|
31
|
+
場合の数的に考えると、1度のクエリで2増える、2減る、0なのでどちらか反転させてもう一度投げてみる*2なので、それぞれ
|
32
|
+
|
33
|
+
|
34
|
+
|
35
|
+
1query/2bit
|
36
|
+
|
37
|
+
2query/2bit
|
38
|
+
|
39
|
+
|
40
|
+
|
41
|
+
で、確率は同じなので平均して3/4 query/bitですね。
|
28
42
|
|
29
43
|
|
30
44
|
|
1
追記
test
CHANGED
@@ -24,7 +24,7 @@
|
|
24
24
|
|
25
25
|
|
26
26
|
|
27
|
-
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4にな
|
27
|
+
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな?(ちゃんと計算してないけど)
|
28
28
|
|
29
29
|
|
30
30
|
|