AGC041-C Domino Quality 全探索・乱択スクリプト

atcoder.jp どの行、列も1*2の畳の数が同じになるようなものを探さないといけない。 解説通りN=4,5,6,7で数が3になるものを探せば、N>=4に対して構成可能だが、N=7を見つけるのが難しかった。 以下はN＝7の例

 .bc.a..
 .bc.a..
 ..aabba
 aab...a
 x.baa..
 x..b.aa
 aa.b.xx

手元では見つからなかったのでpythonでコードを書いた。

N = 7
rs = []
for i in range(3**N):
    # 0:kara, 1:yoko, 2:tate
    s = []
    for j in range(N):
        k, i = i%3, i//3
        s.append(k)
    if sum(s) != 6:
        continue
    for j in range(N):
        if j == 0:
            if s[j] == 1 and s[j+1] != 1:
                break
        elif j == N-1:
            if s[j] == 1 and s[j-1] != 1:
                break
        else:
            if (s[j] == 1) and (s[j+1] != 1 and s[j-1] != 1):
                break
    else:
        rs.append("".join(map(str,s)))
# rs : 行の候補

r2s = []
for i in range(len(rs)):
    for j in range(len(rs)):
        for k, c in enumerate(rs[i]):
            if c == '1' and rs[j][k] != '1':
                break
        else:
            r2s.append((rs[i], rs[j]))
print(len(r2s))

def isok(r):
    for i in range(N):
        t = []
        for j in range(N):
            if r[j][i] == "1":
                t.append(2)
            elif r[j][i] == "2":
                t.append(1)
            else:
                t.append(0)
        if sum(t) != 6:
            return False
        for j in range(N):
            if j == 0:
                if t[j] == 1 and t[j+1] != 1:
                    return False
            elif j == N-1:
                if t[j] == 1 and t[j-1] != 1:
                    return False
            else:
                if (t[j] == 1) and (t[j+1] != 1 and t[j-1] != 1):
                    return False
    return True
from random import randint
c = 0
while True:
    c += 1
    k = [rs[randint(0, len(rs)-1)] for i in range(N)]
    if isok(k):
        print("\n".join(k))
        break
    if c %1000000 == 0:
        print(c)

pypyで試すと数分で解が見つかった。まず行の候補を構成すると130通り見つかる。（行に畳が３つの条件） 130個を7行に適当に置きながら正解を見つける。130**7の探索が必要だが解がたくさんあるのか6*10**7ループ付近で解は見つかった。 これが現実的な速度で見つかるのかどう見当をつけていいのかわからなかった。行の組み合わせ探索時に上手く条件を使えば探索空間をもっと小さくできるとも思うけど。

twitterで探してみても手元で見つけることができた人ばかりだし、これくらいは見つけられる人が多いらしい。難しい。