水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.305 鍵(2)

回答

#60773 No.305 鍵(2) - yukicoder

今度は桁数が大きいため,単純な総当りではダメです.
幾つか解決方法があると思いますが,私の解決方法を.

このクエリは,投げると X locked のように帰ってきて,Xがいくつ合っていたのか,という情報を取れます.
というわけで,ある桁から0から1ずつ変えてみて,前回までの結果と一致数が異なっていれば,その桁についてはあたっているかどうかを確定できることがわかります.
現在"i"を見ているとすると,現在の一致数>前回の一致数の場合,iがその桁では一致している数とみなせます.
現在の一致数<前回の一致数の場合,i-1がその桁では一致している数とみなせます(もしかしてこれ成立するの,0と1をチェックした場合のみかも)
現在の一致数=現在の一致数の場合,その桁についてはまだあっている数がわからないので,iを1増やします….

みたいな方針で調べれば,全探索といえど,回数はかなり抑えることが出来ます.


コンテスト中に解くことが出来てよかった…

res = ""
cnt = 0
curdigit = 0
lastnum = -1
while res != "unlocked" do
    inp = format("%010d", cnt)
    puts inp
    STDOUT.flush
    num, res = gets.chomp.split(" ")
    num = num.to_i
    if num == 10
        break
    end
    if lastnum == -1
        cnt += 10 ** curdigit
        lastnum = num
    elsif lastnum < num
        curdigit += 1
        lastnum = -1
    elsif lastnum > num
        cnt -= 10 ** curdigit
        curdigit += 1
        lastnum = -1
    else
        cnt += 10 ** curdigit
        lastnum = num
    end
end