質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

5回答

1176閲覧

与えられたnビットの入力に対して、正解のビットとの距離が返されるので、ビット数+1以内のクエリで正解ビットを当てたい

ijuya_yika

総合スコア50

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

2グッド

2クリップ

投稿2018/10/25 16:13

###やりたいこと
正解ビットが存在します。
与えられたnビットの入力に対して、正解のビットとの距離が返されるので、ビット数+1以内のクエリで正解ビットを当てるプログラムを書きたいのですがどのようにすれば良いでしょうか?

例えば正解ビットが000101だとします。

最初のクエリが000000と当ててみます。
正解ビットとクエリビットでは4ビットあっているので4が返却されます。

次に000100と当ててみます。
正解ビットとクエリビットでは最後の1以外あっているので5が返却されます。

といった具合です。
最後のクエリでビット数 or 0が返却されたら正解ビットが分かるので終了します。

###試したこと
まず000000で何ビットが0なのか調べる、、、という所までしかできていません。

x_x, set0gut1👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

ベストアンサー

正解
000101

クエリ
000000 -> 4
000001 -> 5
000010 -> 3
000100 -> 5
001000 -> 3
010000 -> 3
100000 -> 3

てな感じにやりまして、全部0のときより増えてればそこは1、減ってりゃ0でありんす。


■追記: 改善方法、長考した結果

あんま綺麗なコードじゃなくて恐縮なんですが、二分探査的に置き換えていって、連続した0または1を検出したらそこで足切りする方法試してみました。

長さ 1000 で 10 回計測したところ、クエリ回数が平均 717.5 となりました。

# coding: utf-8 import random def make_string(int_array): return "".join(map(str, int_array)) LENGTH = 1000 REAL_ANSWER = make_string([random.randint(0, 1) for i in range(LENGTH)]) print "REAL_ANSWER:\t" + REAL_ANSWER count = 0 def check(query): global count count += 1 print "query (" + str(count) + "):\t" + query ret = 0 for i in range(0, len(query)): if query[i] == REAL_ANSWER[i]: ret += 1 return ret NUM_OF_ZERO = check(make_string([0] * LENGTH)) my_answer = [0] * LENGTH # 引数 todo: 訂正すべき数 def solve(begin, end, todo): middle = (begin + end) / 2 tmp_array = [0] * LENGTH for i in range(begin, middle): tmp_array[i] = 1 tmp_score = check(make_string(tmp_array)) left_todo = (tmp_score - NUM_OF_ZERO + middle - begin) / 2 right_todo = todo - left_todo if (left_todo == 0): pass elif (left_todo == middle - begin): for i in range(begin, middle): my_answer[i] = 1 else: solve(begin, middle, left_todo) if (right_todo == 0): pass elif (right_todo == end - middle): for i in range(middle, end): my_answer[i] = 1 else: solve(middle, end, right_todo) solve(0, LENGTH, LENGTH - NUM_OF_ZERO) print "my_answer:\t" + make_string(my_answer) print make_string(my_answer) == REAL_ANSWER

投稿2018/10/25 16:20

編集2018/10/26 00:33
set0gut1

総合スコア2413

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ijuya_yika

2018/10/25 16:24

ご回答ありがとうございます。ご回答のアルゴリズムでできそうですね。もしビットの数が大きくなった場合クエリの数を極力減らす為にはどうすれば良いでしょうか?
hichon

2018/10/25 22:30

正解ビットが1ビット増える毎にクエリが1回必要になるので最大n回のクエリが必要になります。
set0gut1

2018/10/25 22:33

二分探査的に行うと、連続した0または1を発見したときにクエリ回数を節約できるかも…とかはちょっと思ってます。
set0gut1

2018/10/26 00:30

アイデアを実装してみたので回答に追記します。
ijuya_yika

2018/10/26 01:59 編集

ご回答(しかもサンプルコードまで!)ありがとうございます。 41行目に left_todo = (tmp_score - NUM_OF_ZERO + middle - begin) / 2 とあるのですがこの部分のコード作成の思考過程を教えて頂いてもよいでしょうか?
set0gut1

2018/10/26 02:28

それは何パターンか並べて観察した結果、帰納的に得られた式でして、正しいと証明はできるのですが、あんまり釈然としない気持ちで書きました。
guest

0

範囲を広げ、その範囲を再帰的に二分割しながら探索すれば早く終わることもあります。

正解が 000011 の場合
000000 と比較して 4 ポイント
次に前半を反転した 111000 と比較して 1 ポイント
3 ビット反転して 3 ポイント減ったので前半の 000 が確定します。

後半を更に二分割し、前半 1 ビットと後半 2 ビットに分けます。
1 回目の前半が 000 で確定したので、これと 2 回目の前半を反転した 1 と 2 回目の後半 00 を合わせて 000100 と比較します。

結果は 3 ポイントとなり、100 が全て間違っていることが確定します。
それで 000011 という正解が 3 回の比較で得られました。

投稿2018/10/25 23:35

編集2018/10/25 23:38
Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2018/10/25 23:43

ただ、これはクエリの提出にコストがかかる場合の話で、結局 1 ビットずつ比較した方が複雑な演算をするより早く終わる可能性もあります。
Zuishin

2018/10/25 23:59

また、こういうやり方もあります。 001101 と 000000 を比較して 3 ポイント得られたら 0 が 3 つ 1 が 3 つあることが確定します。 この数で得られる組み合わせ全てと比較し、6 ポイント得られればその値で終了、0 ポイントなら反転して終了です。
opyon

2018/10/26 00:17

私も2分探査で試そうとしていましたが要件が未定なので回答で書いていたものは削除しました。 結局極端に1が少ない時に0000がヒットすれば判明出来るけど1が多くてバラけていると全部探索する必要があることになるのでn桁回探索すれば済む話かなと。 例えば16桁で1000 0000 1010 0010 などが正解の場合などを試していました。
Zuishin

2018/10/26 00:34

1 が多い時も使えます。1111 と 0000 を比較してポイント 0 だと確定するので。 0 と 1 の数が均等で配置も均等な時に最も時間がかかりますが、だいたいどこかの部分に偏るので期待値は高いと思います。 3 ビットの場合、ほとんどの場合 1 回、最悪 2 回の比較で確定できるので、回数だけ言えば全探索に比べて必ず 2/3 以下の比較回数になります。
opyon

2018/10/26 00:40

なるほど。アルゴリズム的に考えれば全探索を1とした場合より回数が少しでも少なければ最適解ということですね。 実装で考える癖で1万桁でも1万回探索しても数ミリ秒だし大差ないなと思いこんでしまいました。
Zuishin

2018/10/26 01:08

例えばビット数が多くクエリに通信が絡むと差が出ます。 差が出ないまたは逆転するようなら条件が整っていないので演算を単純化した方がいいかも知れません。
guest

0

適当に思いついたやつを。ミスがあるかもしれません。

1 適当なn bitのクエリを作り、投げて「前の値」として記録する
2 先頭2 bitを反転させてクエリを投げ、
2.a 値が2増えたら「前の値」を2加算して次の2 bitを見る(2つとも間違っていたパターン)
2.b 値が2減ったら元に戻して次の2 bitを見る(2つとも正解だったパターン)
2.c 値の変化が0だったら2 bitのうちどちらかを反転させてもう一度クエリを投げ、(どちらか正解でどちらか間違いのパターン)
2.c.a 値が1増えたら「前の値」を1加算して次の2 bitを見る
2.c.b 値が1減ったら両方反転してから「前の値」を1加算して次の2 bitを見る

(途中で値がnに達したら打ち切る)
(nが奇数だった場合の端数の処理は考慮していない)

やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな。

場合の数的に考えると、1度のクエリで2増えるor2減る、0なのでどちらか反転させてもう一度投げてみる*2のどちらかなので、それぞれ

1query/2bit
2query/2bit

で、確率は同じなので平均して3/4 query/bitですね。

2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか? は検討していません。宿題とします(私の)。

投稿2018/10/25 22:41

編集2018/10/25 23:00
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hayataka2049

2018/10/25 23:02 編集

一般のmbitずつ見た場合について検討したいが、なんとなく大して良くならなさそうな感じがする上にちょっと面倒くさい
set0gut1

2018/10/26 00:31

近いことやってみたんですが大して良くならなかったです。
hayataka2049

2018/10/26 02:58 編集

けっきょくこの問題、クエリ回数に関してO(n)以下になるのかならないのか、よくわからないです。二分探索なら期待できる気もするけど、なんとなく収束級数じみてるというか、けっきょく定数倍? みたいな
swordone

2018/10/26 02:49

1ビットずつチェックする方法だと、1回のチェックで返ってくる結果の可能性は2パターンなので、総パターン2^nに対して候補を半分ずつそぎ落としていくことになるからO(n)になる。 理論上、1回のチェックでの結果のパターン数が多くなればオーダーは減るはず。 ただ、増える結果のパターンをどう処理するかが難しそうだが…
set0gut1

2018/10/27 10:14

なんか O(log N) の解法がありそうな雰囲気は感じてて、心に引っかかりますね
hayataka2049

2018/10/27 11:19 編集

私はO(N)にしかならない雰囲気を感じていて、ほぼ確信を抱いているのですが、証明する手順が思いつかないので心に引っかかっています
guest

0

もしビットの数が大きくなった場合クエリの数を極力減らす為にはどうすれば良いでしょうか?

最下位から最上位まで調べる方法では
110000100001だとどんなに桁数が多くても結局最初から最後まで探索する必要があるかと。
001100000011などの途中で打ち切り出来る時に少しだけ早く終る程度です。
最長でn-1回の探索であればこれ以上速くなることは無いのではないでしょうか。

余談ですが・・・
極端な例ですと1万桁で正解の1が1個の時に最下位1と最上位1であれば約1万回差が出ます。
もし要件として桁数が数万桁でとても大きくて1が極端に少ないなら2分探索などが可能かなと。
要件が不明なのであしからず。

総桁数をnとした場合
000000で出た答えa
n-a1の数となる

最下位ビットから最上位ビットまで最長ループでn-1回探索する
途中で正解が分かったら以降そこには1を立てる
探索範囲の残りと答えの残りが同じなら残りは全て答えとなるので探索を打ち切れる

以下総桁数n=6桁,1の数a=2個のパターン

探索範囲の最初に正解がある場合最短
000011 -> 6 正解

000000 -> 4 残り2
000001 -> 5 残り1
000011 -> 6 終了

探索範囲の最後に正解がある場合最長
110000 -> 6 正解

000000 -> 4 残り2
000001 -> 3
000010 -> 3
000100 -> 3
001000 -> 3 残り2 == 探索範囲の残り2なので残り全てが答え

探索範囲の途中に正解がある場合
001100 -> 6 正解

000000 -> 4 残り2
000001 -> 3
000010 -> 3
000100 -> 5 残り1
001100 -> 6 終了

探索範囲の途中と最後に正解がある場合最長n+1回
100100 -> 6 正解

000000 -> 4 残り2
000001 -> 3
000010 -> 3
000100 -> 5 残り1
001100 -> 4 残り1
010100 -> 4 残り1==探索範囲の残り1なので最後のビットが正解となる
100100 -> 6 終了

投稿2018/10/25 22:27

opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

こんな漢字で、
1.適当なnビットのクエリを作成し正解数を得る。
2.クエリの最初のビットを反転し正解数を得る。
3.正解数が増えていればクエリの次のビットを反転し、減っていれば前と次のビットを反転し正解数を得る。
4.3を正解数がnになるまで繰り返す。

投稿2018/10/25 21:27

hichon

総合スコア5737

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問