結果

問題 No.2926 Botaoshi
ユーザー kusirakusirakusirakusira
提出日時 2024-09-01 16:28:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 211 ms / 2,000 ms
コード長 1,028 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 103,432 KB
最終ジャッジ日時 2024-10-06 13:52:46
合計ジャッジ時間 7,502 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,468 KB
testcase_01 AC 45 ms
52,128 KB
testcase_02 AC 40 ms
52,864 KB
testcase_03 AC 40 ms
52,864 KB
testcase_04 AC 44 ms
51,948 KB
testcase_05 AC 39 ms
52,808 KB
testcase_06 AC 39 ms
53,204 KB
testcase_07 AC 39 ms
52,464 KB
testcase_08 AC 38 ms
52,868 KB
testcase_09 AC 39 ms
52,564 KB
testcase_10 AC 45 ms
52,468 KB
testcase_11 AC 47 ms
52,468 KB
testcase_12 AC 211 ms
103,168 KB
testcase_13 AC 162 ms
102,272 KB
testcase_14 AC 162 ms
102,512 KB
testcase_15 AC 40 ms
53,368 KB
testcase_16 AC 140 ms
95,472 KB
testcase_17 AC 154 ms
99,676 KB
testcase_18 AC 85 ms
79,396 KB
testcase_19 AC 129 ms
91,936 KB
testcase_20 AC 101 ms
83,408 KB
testcase_21 AC 126 ms
89,132 KB
testcase_22 AC 136 ms
91,468 KB
testcase_23 AC 79 ms
78,392 KB
testcase_24 AC 147 ms
93,472 KB
testcase_25 AC 97 ms
81,084 KB
testcase_26 AC 147 ms
96,848 KB
testcase_27 AC 116 ms
89,180 KB
testcase_28 AC 71 ms
78,744 KB
testcase_29 AC 68 ms
77,456 KB
testcase_30 AC 90 ms
83,172 KB
testcase_31 AC 86 ms
79,464 KB
testcase_32 AC 106 ms
85,280 KB
testcase_33 AC 140 ms
95,544 KB
testcase_34 AC 132 ms
92,720 KB
testcase_35 AC 65 ms
70,588 KB
testcase_36 AC 169 ms
103,432 KB
testcase_37 AC 169 ms
103,012 KB
testcase_38 AC 179 ms
103,424 KB
testcase_39 AC 171 ms
103,268 KB
testcase_40 AC 170 ms
103,264 KB
testcase_41 AC 151 ms
103,012 KB
testcase_42 AC 146 ms
103,016 KB
testcase_43 AC 147 ms
103,028 KB
testcase_44 AC 144 ms
101,232 KB
testcase_45 AC 143 ms
101,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
S = list(input())
mod = 998244353
# dp[i][j] := i番目の棒までの倒し方を決めて、i番目の状態がjであるときの通り数
# 0=>U, 1=>L, 2=>R
dp = [[0 for j in range(3)] for i in range(n+1)]
dp[0][0] = 1


for i in range(n):
    for j in range(3):
        
        # 倒す方向が決まっている場合
        if(S[i] == "U"):
            dp[i+1][0] += dp[i][j]
            dp[i+1][0] %= mod
            
        elif(S[i] == "L"):
            # R→Lの遷移禁止
            if(j == 2):
                continue
            dp[i+1][1] += dp[i][j]
            dp[i+1][1] %= mod
        elif(S[i] == "R"):
            dp[i+1][2] += dp[i][j]
            dp[i+1][2] %= mod
        
        # 自由に倒してよい場合
        elif(S[i] == "."):
            for k in range(3):
                # R→Lの遷移禁止
                if(j==2 and k==1):
                    continue
                dp[i+1][k] += dp[i][j]
                dp[i+1][k] %= mod
    
print(sum(dp[-1]) % mod)
0