結果

問題 No.1766 Tatsujin Remix
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:32:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 278 ms / 2,000 ms
コード長 4,264 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 150,848 KB
最終ジャッジ日時 2025-03-20 20:33:47
合計ジャッジ時間 5,901 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    S = ''.join(input[1:N+1])
    len_S = len(S)
    
    # Precompute allowed characters for each position
    allowed = []
    for i in range(len_S):
        c = S[i]
        if c != '.':
            allowed.append([c])
        else:
            # Check i+1
            if i+1 < len_S:
                next_c = S[i+1]
                if next_c == '.':
                    opts = ['d', 'k', '.']
                else:
                    opts = ['d', 'k', '.']
                    if next_c in opts:
                        opts.remove(next_c)
            else:
                opts = ['d', 'k', '.']
            allowed.append(opts)
    
    # Initialize DP table
    dp = [ [[0]*2 for _ in range(2)] for __ in range(len_S+1)]
    dp[0][0][0] = 1  # before processing any character
    
    for i in range(len_S):
        current_opts = allowed[i]
        for prev_dot in [0, 1]:
            for must_current in [0, 1]:
                current_val = dp[i][prev_dot][must_current]
                if current_val == 0:
                    continue
                
                # Process current position i
                # Check if current is forced to be dot
                if must_current:
                    # Only '.' is allowed if it is in current_opts
                    if '.' in current_opts:
                        opt = '.'
                    else:
                        continue
                    # Check conditions for selecting '.'
                    is_odd = (i+1) % 2
                    if is_odd:
                        # i is 0-based; the actual pos is i+1 which is odd
                        if i+1 >= 2:  # actual position >=2, so i (0-based) >=1?
                            if not prev_dot:
                                continue
                    # Determine must_next
                    if (i+1) % 2 == 1:  # current is i+1 (1-based) which is odd
                        # Actual next is i+1 (0-based)
                        if i+1 < len_S:
                            must_next = True
                        else:
                            must_next = False
                    else:
                        must_next = False
                    
                    new_prev_dot = 1
                    new_must = must_next
                    # Update next state
                    dp[i+1][new_prev_dot][new_must] = (dp[i+1][new_prev_dot][new_must] + current_val) % MOD
                else:
                    # Try all possible opts
                    for opt in current_opts:
                        new_prev_dot = 1 if opt == '.' else 0
                        is_odd = (i+1) % 2
                        must_next = False
                        valid = True
                        
                        if opt == '.':
                            if is_odd:
                                if i+1 >= 2:  # check previous
                                    if not prev_dot:
                                        valid = False
                                # Must set must_next if next exists and is current's parity leads to it
                                # Determine if i+1 is a position that needs to be dot
                                # Because current is odd and opt is '.', next position must be dot if exists
                                if i+1 < len_S:
                                    must_next = True
                        
                        if valid:
                            if i+1 <= len_S - 1:
                                dp[i+1][new_prev_dot][must_next] = (dp[i+1][new_prev_dot][must_next] + current_val) % MOD
                            else:
                                # No next position, so must_next must be False
                                if not must_next:
                                    dp[i+1][new_prev_dot][0] = (dp[i+1][new_prev_dot][0] + current_val) % MOD
    
    # Sum all valid states after processing all positions
    total = 0
    for prev_dot in [0, 1]:
        for must_current in [0, 1]:
            total = (total + dp[len_S][prev_dot][must_current]) % MOD
    print(total)

if __name__ == '__main__':
    main()
0