読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

はてなブログはクソなのでやめます => https://hackmd.io/s/SyQBwu6Kg#

No.355 数当てゲーム(2) - yukicoder

No.355 数当てゲーム(2) - yukicoder プロコン

Sat Apr 2 00:01:45 JST 2016

No.355 数当てゲーム(2) - yukicoder

いわゆるヒットアンドブローのAIを書くもの インタラクティブに結果を受け取るタイプの問題

この問題の註意すべき細かい点としては、

  1. 4桁は全て異なる
  2. 結果として返ってくる2つの数値は重ならない (たいていそうだけど)

難しくない解法

100回以内のトライで正答したい 私の解法は大きく2つのフェーズからなる

  1. 使われてる4文字をあてる
  2. 並び替える

並び替えが 24通りなので、4文字を当てるのを76回以内でやればok. ただ貪欲法でやればいい. 大雑把に言えば、各桁が10通りで、 4 \times 10 通り (4桁が全て異なる場合だけを使うこと) 試す. 詳細に言うと、返ってくる2つの値の和が「使われてる文字」の数なので、これについての貪欲法を行う.

4文字を当てられたら、もう24通り全部試すだけ

yukicoderのインタラクティブ系統は、ゲームが終わったらそれ以降にだらだら出力せずにさっさと終了しないとREだかTLEだかを食らう.

http://yukicoder.me/submissions/84671

def torai(a) # try
  puts a*' '
  STDOUT.flush
  gets.split.map(&:to_i)
end

a = [0,1,2,3]
n,m = torai(a)
exit 0 if n == 4
k = n+m

for i in 0..3 do
  for x in 0..9 do
    if not a.include?(x)
      b = a.clone
      b[i] = x
      n,m = torai(b)
      if n==4
        exit 0
      end
      if k < (n+m)
        k = n+m
        a = b
        break
      end
      if k > (n+m)
        break
      end
    end
  end
end

a.permutation(4) {|a,b,c,d|
  puts [a,b,c,d]*' '
  STDOUT.flush
  n,m=gets.split.map(&:to_i)
  if n==4
    exit 0
  end
}