Moving Floors and a Switch

2 secs 1024 MB

スライムの配置は $2^{HW}$ パターンだけあり、動く床の状態は A, B の2パターンだけあります。
そのため、鳩の巣原理より $2 \times 2^{HW}$ 秒後までに、必ず配置パターンの変化にループが生じます。
よって、ループが生じるまでスライムの移動をシミュレーションすれば良いです。
ループに入るまでに $t_{\mathrm{offset}}$ 秒、ループを $1$ 周するのに $t_{\mathrm{loop}}$ 秒だけかかるとすると、 $t$ 秒後のスライムの配置は、

$t < t_{\mathrm{offset}}$ なら $t_{\mathrm{offset}}$ 秒後のシミュレーション結果
$t \geq t_{\mathrm{offset}}$ なら $(t - t_{\mathrm{offset}})$ を $t_{\mathrm{loop}}$ で割った余りを $t_r$ として、 $t_r$ 秒後のシミュレーション結果

となります。

なお、スライムは動く床に従って規則的に移動するため、実際に取り得る配置パターン数 $P$ は $2 \times 2^{HW}$ に比べて非常に小さくなります。

$1$ 秒毎のスライムの移動は、動く床の数 $HW$ に比例した時間でシミュレーションできるので、計算量は全体で $O(HWP)$ です。

想定解（Python3）

xxxxxxxxxx
 
from copy import deepcopy
​
def arrangement2code(arrangement):
    code = 0
    for i in range(H):
        for j in range(W):
            if arrangement[i][j] == '#':
                code += 1 << (i*W + j)
    return code
​
def code2arrangement(code):
    arrangement = [['.']*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if (code >> (i*W + j)) % 2 == 1:
                arrangement[i][j] = '#'
    return arrangement
​
H, W, t, i_s, j_s = map(int, input().split())
i_s, j_s = i_s - 1, j_s - 1
A = [[list(input()) for _ in range(H)],
     [list(input()) for _ in range(H)]]
S = [list(input()) for _ in range(H)]
​
d = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
state = 0
​
transition = [arrangement2code(S)]
for _ in range((1 << (H*W+1))):
    S_ = [['.']*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                dh, dw = d[A[state][i][j]]
                S_[i + dh][j + dw] = '#'
​
    code = arrangement2code(S_) + (state << (H*W))
    if code not in transition:
        transition.append(code)
        S = deepcopy(S_)
    else:
        break
    
    if S_[i_s][j_s] == '#':
        state ^= 1
​
idx = transition.index(code)
offset = transition[:idx]
loop = transition[idx:]
if t < len(offset):
    T_code = offset[t]
else:
    T_code = loop[(t - len(offset)) % len(loop)]
T = code2arrangement(T_code)
for i in range(H):
    print(''.join(T[i]))