結果

問題 No.2926 Botaoshi
コンテスト
ユーザー KA37RI
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

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