結果

問題 No.1766 Tatsujin Remix
コンテスト
ユーザー LyricalMaestro
提出日時 2025-06-14 19:48:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 620 ms / 2,000 ms
コード長 3,627 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 78,504 KB
最終ジャッジ日時 2025-06-14 19:48:26
合計ジャッジ時間 6,602 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1766

MOD = 998244353

def main():
    N = int(input())
    S = []
    for _ in range(N):
        S.append(input())
    S = "".join(S)

    # 初期設定
    dp = {}
    for w0 in [".", "d", "k"]:
        if S[0] != ".":
            if w0 != S[0]:
                continue
            for w1 in [".", "d", "k"]:
                if S[1] != ".":
                    if w1 != S[1]:
                        continue
                    w = w0 + w1
                    dp[w] = 1
                else:
                    w = w0 + w1
                    dp[w] = 1
        else:
            if w0 == ".":
                if S[1] == ".":
                    dp[".."] = 1
            else:
                for w1 in [".", "d", "k"]:
                    if S[1] != ".":
                        if w1 != S[1]:
                            continue
                        w = w0 + w1
                        dp[w] = 1
                    else:
                        w = w0 + w1
                        dp[w] = 1
    if S[0] == "." and S[1] != ".":
        new_dp = {}
        for key, value in dp.items():
            if key[0] == S[1]:
                continue
            new_dp[key] = value
        dp = new_dp

    for i in range(2, len(S)):
        new_dp = {}
        if S[i] != ".":
            if S[i - 1] != ".":
                for key, value in dp.items():
                    if S[i - 1] == key[1]:
                        new_key = key[1] + S[i]
                        if new_key not in new_dp:
                            new_dp[new_key] = 0
                        new_dp[new_key] += value
                        new_dp[new_key] %= MOD
            else:
                for key, value in dp.items():
                    if key[1] == S[i]:
                        continue
                    if key[1] == "." and (i % 2 == 1):
                        continue
                    new_key = key[1] + S[i]
                    if new_key not in new_dp:
                        new_dp[new_key] = 0
                    new_dp[new_key] += value
                    new_dp[new_key] %= MOD
        else:
            if i % 2 == 0:
                # 奇数番号
                for key, value in dp.items():
                    for w in [".", "d", "k"]:
                        if w == "." and key[1] != "." :
                            continue
                        new_key = key[1] + w
                        if new_key not in new_dp:
                            new_dp[new_key] = 0
                        new_dp[new_key] += value
                        new_dp[new_key] %= MOD
            else:
                # 偶数番号
                for key, value in dp.items():
                    if key in ("d.", "k."):
                            continue
                    elif key == "..":
                        new_key = ".."
                        if new_key not in new_dp:
                            new_dp[new_key] = 0
                        new_dp[new_key] += value
                        new_dp[new_key] %= MOD
                    else:
                        for w in [".", "d", "k"]:
                            new_key = key[1] + w
                            if new_key not in new_dp:
                                new_dp[new_key] = 0
                            new_dp[new_key] += value
                            new_dp[new_key] %= MOD
        dp = new_dp

    answer = 0
    for value in dp.values():
        answer += value
        answer %= MOD
    print(answer)



                            






            





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