狠狠撸

K : Batch Style Mastermind
Writer:tomerun
Tester:komiya

問題概要
●
9桁の数でマスターマインドをやる。
– 数字の重複や先頭0は許す。
●
答えを推測するため、9桁の整数文字列9
個を同時に送信し、その結果の (hit
数,blow数) の組がシャッフルされて返さ
れる。
●
同じ文字列は複数回使えない。
●
このクエリ9回以内（部分点は20回以
内）で答えを当てよ。
Autumn Fest 2012

重要な事実
●
使う数字は0-9の10個あって、答えは9桁なの
で、使われない数字が少なくとも1つはある。
●
使われない数字をXとする。次のようなクエリ
を投げると、例えば答えが ”123045607” の
場合の結果は、右側に示した通りになる。
0XXXXXXXX => (0,1)
00XXXXXXX => (0,2)
000XXXXXX => (0,2)
0000XXXXX => (1,1)
00000XXXX => (1,1)
000000XXX => (1,1)
0000000XX => (1,1)
00000000X => (2,0)
000000000 => (2,0)
Autumn Fest 2012

重要な事実
●
実際にはこれらの9個のペアがシャッフルされ
て返されるが、ソートしてやれば前のページに
示した順に並ぶ。
●
上から順に見て、hit数がどこで増えたかを調べ
ることで0が答えのどの位置にあるかを決定で
きる。

●
以降、答えの中に数字dが何回現れるかをc[d]
で表す。

Autumn Fest 2012

解法
●
大まかに、場合分けを交えて決定的に決めてい
く方針と、ランダム性を入れて探索する方針が
ある。
●
後者の方がおそらく楽。
●
（最初は探索はTLEにしたかったのだけど思い
の外速くて通ってしまった）

Autumn Fest 2012

場合分け解法Easy:Part1
●
まず次のクエリを投げる。
000000000
下8個について、hit数+blow数
123456789
●
234567891
345678912 は等しくなるので、9個の (hit
456789123
数, blow数) ペアのうちhit数
+blow数が他の8個と異なるも
567891234
678912345
789123456 のがc[0]となる（9個全部同じ
891234567
だったらそれがc[0]）。
●
これを数字を入れ替えて1~8についても行う
と、c[1]?c[8]がわかる（c[9]については残り
なので調べなくてもわかる）。
Autumn Fest 2012

場合分け解法Easy:Part2
●
ここまでで、少なくとも1つの「使われない数
字」がわかるので、「重要な事実」のページで
示した方法を使って他の数字がどの桁にあるか
を決める。残り9個の数字のうち8個について
行えば十分。
●
注意：”000000000”のように全てが同じ数字
で構成される文字列はすでにPart1で使ってい
るので、1文字だけ他の数字を入れる。
– “000000000”の結果=(c[0], 0) は既に知っている
ので、クエリ結果の(hit,blow)をソートした後に一
番最後のものを取り除いて代わりに(c[0], 0)を入れ
れば良い
Autumn Fest 2012

場合分け解法Easy
●
Part1でクエリ9回、Part2でクエリ8回、合計
17回で答えが決まる。

Autumn Fest 2012

場合分け解法Hard:Part1
●
まず次のクエリを投げる。
000000000 ●
この結果の9個の(hit数,blow数)
000000001 ペアのうち、max(hit数+blow
数)==c[0]+c[1] となる。
000000011
000000111
000001111
000011111
●
答えが”111111111”の場合だけ
000111111 は例外だが、その場合もとりあ
001111111 えずc[0]+c[1]=8だと思っておい
011111111
て大丈夫。
●
これを0と1だけでなく、2と3、4と5…と順に
行い、初めてc[2i]+c[2i+1]<=1となったところ
でストップする（そうなるiは必ず存在する）。
Autumn Fest 2012

●
i==dのところでストップしたとする。
●
c[2d]+c[2d+1]==0の場合、2dも2d+1も一度
も答えの中に現れない。
●
c[2d]+c[2d+1]==1の場合、クエリ結果に(0,0)
が現れるならc[2d]==0、そうでなければ
c[2d+1]==0。また、9個のhit数の合計を見る
ことで1つ現れた数字の位置もわかる。

●
ということで一度も答えに使われない数字がわ
かったので、これを使って残りを決めていく。

Autumn Fest 2012

场合分け解法贬补谤诲:笔补谤迟2
【Ⅰ】i<2dの範囲について
●
これらの数字については一度クエリを投げてい
るので、その結果を利用しつつ決める。

【Ⅰ-1】c[i]+c[i+1]>=4の場合
●
iとi+1双方について、それぞれ「重要な事実」
のページで示した方法を使ってどの桁にあるか
決めれば良い。

Autumn Fest 2012

【Ⅰ-2】c[i]+c[i+1]==3の場合
●
Part1で行ったクエリ結果のhit数とblow数の
18個の整数を合計することで、c[i]とc[i+1]を
推測できる。

【Ⅰ-2-1】hit数とblow数の合計==25の場合
●
c[i]==2, c[i+1]==1しかありえない。
●
iについて1クエリ使ってどの位置にあるか決め
ると、Part1で行ったクエリ結果の合計hit数の
うち、iによる寄与分を差し引くことができる。
それにより、1つのi+1の位置も特定できる。
Autumn Fest 2012

●
c[i]==1,c[i+1]==2 または c[i]==3,c[i+1]==0
の二通りがあり得る。
●
i+1について1クエリ使ってどの位置にあるか決
めると、どっちのパターンなのかわかる。
●
c[i+1]==2だった場合は、【Ⅰ-2-1】と同様に
して残り1つのiの位置を決定できる。
●
c[i+1]==0だった場合は、Part1で行ったクエ
リによってiの位置を決定できる。

Autumn Fest 2012

●
c[i]==0,c[i+1]==3 しかあり得ない。
●
1回のクエリで i+1の位置を決定すれば良い。

●
以上を総合すると、c[i]+c[i+1]==3の場合は追
加の1回のクエリでiとi+1の位置を決定でき
る。

Autumn Fest 2012

【Ⅰ-3】c[i]+c[i+1]==2の場合
●
ひとまず1クエリ使ってi+1の位置を決める。
●
c[i+1]の値によって場合分けする。

【Ⅰ-3-1】c[i+1]==0だった場合
●
Part1で行ったクエリによってiの位置を決定で
きる。

Autumn Fest 2012

【Ⅰ-3-2】c[i+1]==1だった場合
●
Part1で行ったクエリの結果からi+1の寄与を
差し引くことによってiの位置を決定できる。
【Ⅰ-3-3】c[i+1]==2だった場合
●
c[i]==0なのでiについては調べる必要はない。

●
以上を総合すると、c[i]+c[i+1]==2の場合も追
加の1回のクエリでiとi+1の位置を決定でき
る。
Autumn Fest 2012

【Ⅱ】i>=2d+1の範囲について
●
すでに答えが9桁全部決まっていたら何もしな
い。
●
答えに未定の部分がある場合、2d+1?8までの
それぞれの数字について、1回ずつクエリを
使って位置を決める。
●
9は自動的に決まるので調べなくて良い。

Autumn Fest 2012


●
以上の方法により、ほとんどのケースで9回以
内で答えが決まる。

●
ただし、c[0]+c[1]==c[2]+c[3]==4 かつ
c[4]+c[5]==0 の場合だけが例外。
– この場合は、これまでの方法ではPart1で3
回、Part2で4回、Part3で3回の合計10回かかる

Autumn Fest 2012

●
Part2までが終わった時点で答えのうち8桁が決
まっているので、残り1つは6789のうちどの数
字なのかだけが分かれば良い。
●
右のクエリを投げて、結果が(0,0) 666666666
でないものがいくつあるかを数える 777777774
777777747
ことで、残り1つが6789のうちど 777777477
れなのかが分かる、つまりPart3が 888888884
1回のクエリで済む。 888888848
888888488
888884888
888848888

Autumn Fest 2012

場合分け解法Hard:まとめ
●
ものすごく頑張って場合分けをした。
●
9回以下のランダム性無しなクエリで答えが決
まる。

●
ジャッジ解のコード長 : 9222Byte（Java,
ローカルでのテスト用のコード込み）

Autumn Fest 2012

探索解法Easy
●
場合分け解法:Part1 と同じようにして、それぞ
れの数字が答えの中に何回出現するかを調べる
（クエリ9回）。
●
あり得る回答の候補をnext_permutationで列
挙する。このとき、その候補が答えだと仮定し
た場合にこれまで行った9回のクエリの結果に
矛盾していないかを調べて候補を絞る。これで
たいてい候補の数が10個以内まで絞られる
●
あとはランダムな文字列でクエリを投げると、
ほぼ全ての場合に3回以内で候補が1つに決ま
る。
Autumn Fest 2012

探索解法Easy
●
クエリ回数 9回+3回以内=12回以内で答えが
定まる。
●
（厳密に解析できてなくてごめんなさい…）

Autumn Fest 2012

探索解法Hard
●
c[0]?c[9]を決定するのに必要なクエリ回数を
工夫して9回から減らす。
●
まず、次のクエリでc[0]を調べる。
000000000
123456789 ●
c[0]==0の場合は、「重要な事
234567891 実」で示した方法を使っ
て、1?8について答えのどの位
345678912
456789123
567891234 置にあるかを決定する（探索は
678912345
789123456
しない）。
891234567 ●
合計9回のクエリで答えが決ま
る。
Autumn Fest 2012

探索解法Hard
●
c[0]>0の場合は、次に下で示すクエリを投げる

これの結果のhit数+blow数に
111111111 ●
222222220
222222202 は、c[1]が1回、c[2]+1が3
222222022 回、c[3]+1が5回現れることか
ら、c[1],c[2],c[3]が一気にわか
333333330
333333303
333333033 る。
たとえば、9個のhit+blowのうち
333330333
●
333303333
に3が4回現れたとすると、4を
1,3,5の組み合わせで表すには
4=1+3しかないので、
「c[1]==c[2]+1==3」が判明す
る。 Autumn Fest 2012

探索解法Hard
●
数字を入れ替えて、456,789についても同じこ
とをやる。
●
結果、4回のクエリでc[0]?c[9]が判明する。
●
後は探索解法Easyと同じく、候補を列挙してラ
ンダムな値でクエリを投げる

●
合計 4回+3回以内=7回以内で答えが決まる。

Autumn Fest 2012

狠狠撸

Mastermind

Recommended

More Related Content

Similar to Mastermind (14)

More from tomerun (10)

Mastermind