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

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

ただいまの
回答率

87.91%

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

解決済

回答 5

投稿

  • 評価
  • クリップ 2
  • VIEW 877

score 50

やりたいこと

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

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

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

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

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

試したこと

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+5

正解
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/26 09:30

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

    キャンセル

  • 2018/10/26 10:58 編集

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

    キャンセル

  • 2018/10/26 11:28

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

    キャンセル

+2

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

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/26 11:49

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

    キャンセル

  • 2018/10/27 19:14

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

    キャンセル

  • 2018/10/27 20:17 編集

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

    キャンセル

+2

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

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/26 09:34

    1 が多い時も使えます。1111 と 0000 を比較してポイント 0 だと確定するので。
    0 と 1 の数が均等で配置も均等な時に最も時間がかかりますが、だいたいどこかの部分に偏るので期待値は高いと思います。

    3 ビットの場合、ほとんどの場合 1 回、最悪 2 回の比較で確定できるので、回数だけ言えば全探索に比べて必ず 2/3 以下の比較回数になります。

    キャンセル

  • 2018/10/26 09:40

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

    キャンセル

  • 2018/10/26 10:08

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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 終了

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 87.91%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る