結果

問題 No.1427 Simplified Tetris
コンテスト
ユーザー maspy
提出日時 2021-01-06 00:16:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 3,859 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 77,952 KB
最終ジャッジ日時 2024-10-14 10:09:56
合計ジャッジ時間 4,536 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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