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

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

鍵 - yukicoder

プロコン

Fri Dec 4 13:16:32 JST 2015

No.304 鍵(1) - yukicoder

http://yukicoder.me/submissions/62466

3桁なので1000通りしかなく全通り試せばよい. "unlocked" が出てもすぐにプログラムを止めないとWAになるようなので (http://yukicoder.me/submissions/62465) のでちゃんと入力をチェックする.

No.305 鍵(2) - yukicoder

http://yukicoder.me/submissions/62467

今度は10桁になって組み合わせが膨大になる代わりに、正解した桁数が返ってくる

投げる10桁を

 { w_1 \cdot i \cdot w_2 } where  i \in \Sigma, w_1 \in \Sigma^{\ast}, w_2 \in \Sigma^{\ast}, |w_1|+|w_2| = 9;  \Sigma = \{ 0,1,\ldots,9 \}

とする.  w_1,w_2 を固定して、i を 10通り全て試すと、正しい i のときだけ、返ってくる数字 (正しい桁数) が他よりも 1 だけ大きい

というわけで、

  1. 頭の桁から順に 10 通りずつ試す
    • 以降の桁は適当な数字 (例えば 0 で固定)
a = ''
for i in 0 ... 10
  b = a + i.to_s
  b = b + '0' while b.length < 10
  puts b
end
  1. 返って来た数字が一番大きいものを採用して、頭を固定
a = a + i.to_s

あたった桁数について貪欲法と見做せる

広告を非表示にする