AtCoder AGC 041 C - Domino Quality の全探索でハマった

概要

• N=7,Quality=3の時のドミノの置き方の探索にかなり時間がかかった
• $2^{49}\fallingdotseq 10^{15} $の探索を実装するときは、うまく枝を刈る必要がある
• PythonはC++よりも条件によっては20倍以上遅い

pythonでN=7,Quality=3の場合の置き方の探索をした時

(0,0)からドミノを置いて試していく。試す順番は
1.縦向き
2.横向き
3.置かない

これで適した配置１つを見つけるのに 約740[s] かかった。

findPattern.py

import sys
import numpy as np
import datetime

sys.setrecursionlimit(10 ** 7)


def cntQuality(N, grids, num, axis):
    q = 0

    if axis == 0:
        g = grids[num, :]
    else:
        g = grids[:, num]

    last = -1

    for i in range(N):
        d = g[i]

        if last == d or d == 0:
            continue

        q += 1
        last = d

    return q


def dfs(N, grids, pos, num, q):
    x = pos // N
    y = pos % N


    if y == 0 and x != 0:
        qx = cntQuality(N, grids, x-1, 0)
        if qx != q:
            return False

    # end grids
    if x == N and y == 0:
        # valid
        for i in range(N):
            qy = cntQuality(N, grids, i, 1)
            if qy != q:
                return False
        return grids

    # not yet
    pos += 1

    # put vertical
    if y < N-1 and grids[x][y] == 0 and grids[x][y+1] == 0:
        v_num = num + 1
        # v_grids = copy.copy(grids)
        grids[x][y] = v_num
        grids[x][y+1] = v_num
        g = dfs(N, grids, pos, v_num, q)
        if g is not False:
            return g
        grids[x][y] = 0
        grids[x][y+1] = 0

    # put horizontal
    if x < N-1 and grids[x][y] == 0 and grids[x+1][y] == 0:
        h_num = num + 1
        # h_grids = copy.copy(grids)
        grids[x][y] = h_num
        grids[x+1][y] = h_num
        g = dfs(N, grids, pos, h_num, q)
        if g is not False:
            return g
        grids[x][y] = 0
        grids[x+1][y] = 0

    # dont put domino
    g = dfs(N, grids, pos, num, q)
    if g is not False:
        return g

    return False


start = datetime.datetime.now()
print("start", start)


N = 7
q = 3
grids = np.zeros((N, N))
g = dfs(N, grids, 0, 0, q)
end = datetime.datetime.now()
print("end", end)

print(g)

実行結果.txt

start 2020-01-07 18:13:18.477510
end 2020-01-07 18:22:35.768316
[[  1.   1.   2.   2.   3.   3.   0.]
 [  4.   4.   5.   5.   6.   0.   0.]
 [  7.   7.   0.   0.   6.   8.   8.]
 [  0.   0.   9.  10.   0.   0.  11.]
 [  0.   0.   9.  10.   0.   0.  11.]
 [  0.   0.   0.   0.  12.  13.  14.]
 [  0.   0.   0.   0.  12.  13.  14.]]

なんで740[s]もかかったのか？

探索する順番が悪かった模様。

1.横向き
2.縦向き
3.置かない

で探索した場合、1[s]以内で配置が見つかった。
おそらくこの探索順の場合、合致する枝が近くにあるのだろう。

PythonとC++でいくつかパターンを試してみた

※手元で一度しか試してないので、ブレがあると思います

探索順	Python	C++
横->縦->なし	100[ms]	5[ms]
縦->横->なし	740[s]	17[s]
なし->横->縦	430[ms]	10[ms]

結論

• うまく枝刈りできないと、探索順によってはかなり時間の差が生まれる
• このくらいのオーダーだとPythonよりC++を使った方が良さそう