結果

問題 No.1427 Simplified Tetris
ユーザー maspymaspy
提出日時 2021-01-06 00:16:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 3,859 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,408 KB
最終ジャッジ日時 2024-04-22 10:54:10
合計ジャッジ時間 4,963 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
64,384 KB
testcase_01 AC 59 ms
64,256 KB
testcase_02 AC 68 ms
69,760 KB
testcase_03 AC 58 ms
64,128 KB
testcase_04 AC 58 ms
64,512 KB
testcase_05 AC 59 ms
64,640 KB
testcase_06 AC 69 ms
70,784 KB
testcase_07 AC 59 ms
64,512 KB
testcase_08 AC 57 ms
64,512 KB
testcase_09 AC 64 ms
67,968 KB
testcase_10 AC 60 ms
66,432 KB
testcase_11 AC 74 ms
72,064 KB
testcase_12 AC 60 ms
66,432 KB
testcase_13 AC 58 ms
64,256 KB
testcase_14 AC 66 ms
68,736 KB
testcase_15 AC 68 ms
70,912 KB
testcase_16 AC 64 ms
68,608 KB
testcase_17 AC 66 ms
68,608 KB
testcase_18 AC 56 ms
64,768 KB
testcase_19 AC 69 ms
71,424 KB
testcase_20 AC 70 ms
71,552 KB
testcase_21 AC 57 ms
64,512 KB
testcase_22 AC 65 ms
68,608 KB
testcase_23 AC 69 ms
70,144 KB
testcase_24 AC 68 ms
70,016 KB
testcase_25 AC 86 ms
78,408 KB
testcase_26 AC 58 ms
64,896 KB
testcase_27 AC 58 ms
64,512 KB
testcase_28 AC 68 ms
70,400 KB
testcase_29 AC 70 ms
71,680 KB
testcase_30 AC 56 ms
64,256 KB
testcase_31 AC 68 ms
69,888 KB
testcase_32 AC 67 ms
69,888 KB
testcase_33 AC 66 ms
69,248 KB
testcase_34 AC 58 ms
64,384 KB
testcase_35 AC 58 ms
64,640 KB
testcase_36 AC 84 ms
78,208 KB
testcase_37 AC 74 ms
74,368 KB
testcase_38 AC 69 ms
70,528 KB
testcase_39 AC 70 ms
71,552 KB
testcase_40 AC 70 ms
71,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import string

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
dp[A,B,S]
・落下前の意味で、盤面 A 行分決める
・落下後の意味で、盤面 B 行分決める
・最下段に集合 S がマッチされず余っている
→ 遷移前の None or (A, B, S)
"""

def gen_row_patterns(W):
    """
    行方向にマッチできる集合。フィボナッチ数分ある。
    """
    if W <= 1:
        yield 0
        return
    for x in gen_row_patterns(W - 1):
        yield x << 1
    for x in gen_row_patterns(W - 2):
        yield x << 2 | 3

def calc_dp(H, W, S):
    K = len(S)
    put_row = tuple(gen_row_patterns(W))
    full = (1 << W) - 1
    dp = {(A, B): [None] * (1 << W)
          for A in range(H + 1) for B in range(K + 1)}
    dp[0, 0][0] = (0, 0, 0)
    for A in range(H):
        for B in range(min(A, K) + 1):
            if B + (H - A) < K:
                continue
            frm_dp = dp[A, B]
            """
            落下行を使う場合
            """
            to_dp = dp[A + 1, B]
            for s in range(1 << W):
                if frm_dp[s] is None:
                    continue
                for put in put_row:
                    if s & put:
                        continue
                    t = full - s - put
                    to_dp[t] = (A, B, s)
            """
            残す行を使う場合
            """
            if B == K:
                continue
            to_dp = dp[A + 1, B + 1]
            next_row = S[B]
            for s in range(1 << W):
                if frm_dp[s] is None:
                    continue
                if s & next_row != s:
                    continue
                rest = next_row - s
                for put in put_row:
                    if rest & put != put:
                        continue
                    t = rest - put
                    to_dp[t] = (A, B, s)
    return dp

def re_construct(H, W, S, dp, h):
    """
    とりあえず
    横置き：*
    縦起き：@
    """
    yoko = '*'
    tate = '@'
    res = [['.'] * W for _ in range(H)]
    K = len(S)
    full = (1 << W) - 1
    A, B, s = h, K, 0
    while A:
        A1, B1, s1 = dp[A, B][s]
        row = res[A1]
        if B1 == B:
            for i in range(W):
                res[A1][i] = yoko
        else:
            for i in range(W):
                if S[B1] & 1 << i:
                    res[A1][i] = yoko
        # 縦置きする
        for i in range(W):
            if s & 1 << i:
                res[A1][i] = res[A][i] = tate
        A, B, s = A1, B1, s1
    A = res
    # あとはアルファベットを割り当てていく
    alphabets = list(string.ascii_letters)[::-1]
    for h in range(H):
        for w in range(W):
            if A[h][w] == tate:
                a = alphabets.pop()
                A[h][w] = A[h + 1][w] = a
            elif A[h][w] == yoko:
                a = alphabets.pop()
                A[h][w] = A[h][w + 1] = a
    for row in A:
        print(''.join(row))

def main(H, W, S):
    # 値が入っている行数
    K = H
    for x in S:
        if x == 0:
            K -= 1
    # 落下しきっていなくて矛盾している場合
    # 消去すべきなのに消去していない場合
    S = S[H - K:]
    full = (1 << W) - 1
    if any(x in [0, full] for x in S):
        print('No')
        return
    dp = calc_dp(H, W, S)
    for h in range(H + 1):
        if dp[h, K][0]:
            print('Yes')
            re_construct(H, W, S, dp, h)
            return
    print('No')

H, W = map(int, readline().split())
S = []
for i in range(H):
    row = readline().rstrip().decode()
    value = 0
    for j in range(W):
        x = row[j]
        if x == '#':
            value += 1 << j
    S.append(value)

main(H, W, S)
0