結果

問題 No.2926 Botaoshi
ユーザー 👑 KA37RIKA37RI
提出日時 2024-08-05 23:03:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 1,038 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 97,408 KB
最終ジャッジ日時 2024-10-06 13:52:36
合計ジャッジ時間 5,632 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,480 KB
testcase_01 AC 37 ms
52,096 KB
testcase_02 AC 39 ms
52,096 KB
testcase_03 AC 38 ms
51,968 KB
testcase_04 AC 37 ms
52,480 KB
testcase_05 AC 38 ms
52,096 KB
testcase_06 AC 37 ms
52,096 KB
testcase_07 AC 36 ms
52,096 KB
testcase_08 AC 37 ms
52,096 KB
testcase_09 AC 36 ms
52,480 KB
testcase_10 AC 38 ms
51,840 KB
testcase_11 AC 38 ms
52,096 KB
testcase_12 AC 130 ms
97,156 KB
testcase_13 AC 128 ms
96,384 KB
testcase_14 AC 128 ms
96,512 KB
testcase_15 AC 43 ms
59,008 KB
testcase_16 AC 122 ms
90,932 KB
testcase_17 AC 135 ms
94,368 KB
testcase_18 AC 80 ms
79,744 KB
testcase_19 AC 110 ms
87,808 KB
testcase_20 AC 87 ms
81,492 KB
testcase_21 AC 100 ms
85,376 KB
testcase_22 AC 108 ms
87,552 KB
testcase_23 AC 67 ms
73,472 KB
testcase_24 AC 118 ms
89,600 KB
testcase_25 AC 78 ms
79,488 KB
testcase_26 AC 124 ms
92,544 KB
testcase_27 AC 94 ms
85,760 KB
testcase_28 AC 58 ms
68,736 KB
testcase_29 AC 58 ms
67,200 KB
testcase_30 AC 81 ms
81,280 KB
testcase_31 AC 82 ms
79,488 KB
testcase_32 AC 95 ms
82,944 KB
testcase_33 AC 124 ms
91,264 KB
testcase_34 AC 116 ms
88,796 KB
testcase_35 AC 64 ms
69,504 KB
testcase_36 AC 135 ms
97,152 KB
testcase_37 AC 140 ms
97,152 KB
testcase_38 AC 138 ms
97,152 KB
testcase_39 AC 134 ms
96,896 KB
testcase_40 AC 135 ms
97,112 KB
testcase_41 AC 135 ms
97,152 KB
testcase_42 AC 135 ms
97,408 KB
testcase_43 AC 135 ms
96,896 KB
testcase_44 AC 138 ms
96,452 KB
testcase_45 AC 135 ms
96,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 定数および入力
mod = 998244353
n = int(input())
s = input()

# 簡易化のため s の両端に U を追加する（文字列長も 2 伸ばしておく） *1
n += 2
s = "U" + s + "U"

# table[i番目まで見る][0:左に倒す,1:倒さない,2:右に倒す] = その状態の通り数 mod 998244353
table = [[0, 0, 0] for _ in range(n)]

# 初期化
table[0][1] = 1

# i を 1 から n-1 までループ
for i in range(1, n):
	
	# j, k をそれぞれ 0 から 2 までループ
	for j in range(3):
		for k in range(3):
			
			# 右に倒す -> 左に倒す の遷移はスキップ
			if (j, k) == (2, 0):
				continue
			
			# s の i 番目の文字の条件に合わない場合スキップ
			if s[i] in "LUR" and s[i] != "LUR"[k]:
				continue
			
			# 棒 i-1 の状態 j から棒 i の状態 k へ状態数を足し mod をとる
			table[i][k] += table[i-1][j]
			table[i][k] %= mod
			
# この場合答えは最右の棒の棒が倒れていないときの状態数 (*1 の簡易化のため)
print(table[n-1][1])
0