AtCoder AGC 041 C - J'étais accro à la recherche complète de Domino Quality

Aperçu

--Il a fallu beaucoup de temps pour chercher comment placer Domino lorsque N = 7 et Qualité = 3. -Lors de l'implémentation de la recherche de $ 2 ^ {49} \ Fallingdotseq 10 ^ {15} $, vous devez bien élaguer les branches --Python est plus de 20 fois plus lent que C ++ dans certaines conditions

Lorsque vous recherchez comment placer N = 7 et Quality = 3 en python

Placez Domino de (0,0) et essayez-le. L'ordre d'essayer

1. Orientation verticale
2. Sur le côté
3. Ne mettez pas

Il a fallu ** environ 740 [s] ** pour trouver un emplacement approprié.

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)

Résultat d'exécution.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.]]

Pourquoi cela a-t-il coûté 740 [s]?

Il semble que l'ordre de recherche était mauvais.

1. Sur le côté
2. Orientation verticale
3. Ne mettez pas

Lors de la recherche avec, l'arrangement a été trouvé dans un délai de 1 [s]. Peut-être que dans cet ordre de recherche, il y a des branches correspondantes à proximité.

J'ai essayé quelques modèles en Python et C ++

• Je ne l'ai essayé qu'une seule fois, donc je pense qu'il y a un peu de flou.

Conclusion

――Si vous ne pouvez pas bien tailler, il y aura un décalage horaire considérable en fonction de l'ordre de recherche. ――Il semble préférable d'utiliser C ++ que Python pour cette commande.