回答編集履歴
4
追記
answer
CHANGED
|
@@ -20,4 +20,4 @@
|
|
|
20
20
|
|
|
21
21
|
で、確率は同じなので平均して3/4 query/bitですね。
|
|
22
22
|
|
|
23
|
-
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか？ は検討していません。
|
|
23
|
+
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか？ は検討していません。宿題とします（私の）。
|
3
変更
answer
CHANGED
|
@@ -13,7 +13,7 @@
|
|
|
13
13
|
|
|
14
14
|
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな。
|
|
15
15
|
|
|
16
|
-
場合の数的に考えると、1度のクエリで2増える
|
|
16
|
+
場合の数的に考えると、1度のクエリで2増えるor2減る、0なのでどちらか反転させてもう一度投げてみる*2のどちらかなので、それぞれ
|
|
17
17
|
|
|
18
18
|
1query/2bit
|
|
19
19
|
2query/2bit
|
2
追記
answer
CHANGED
|
@@ -11,6 +11,13 @@
|
|
|
11
11
|
（途中で値がnに達したら打ち切る）
|
|
12
12
|
（nが奇数だった場合の端数の処理は考慮していない）
|
|
13
13
|
|
|
14
|
-
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな
|
|
14
|
+
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな。
|
|
15
15
|
|
|
16
|
+
場合の数的に考えると、1度のクエリで2増える、2減る、0なのでどちらか反転させてもう一度投げてみる*2なので、それぞれ
|
|
17
|
+
|
|
18
|
+
1query/2bit
|
|
19
|
+
2query/2bit
|
|
20
|
+
|
|
21
|
+
で、確率は同じなので平均して3/4 query/bitですね。
|
|
22
|
+
|
|
16
23
|
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか？ は検討していません。
|
1
追記
answer
CHANGED
|
@@ -11,6 +11,6 @@
|
|
|
11
11
|
（途中で値がnに達したら打ち切る）
|
|
12
12
|
（nが奇数だった場合の端数の処理は考慮していない）
|
|
13
13
|
|
|
14
|
-
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4にな
|
|
14
|
+
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな？（ちゃんと計算してないけど）
|
|
15
15
|
|
|
16
16
|
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか？ は検討していません。
|