結果

問題 No.2926 Botaoshi
コンテスト
ユーザー urunea
提出日時 2026-11-11 02:05:21
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,575 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,216 ms
コンパイル使用メモリ 197,796 KB
実行使用メモリ 155,864 KB
最終ジャッジ日時 2026-11-11 02:06:04
合計ジャッジ時間 25,536 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 35 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

long long offset = 10;
map<long long, long long> dp;
long long mod = 998244353;

// Pythonの @lru_cache に相当するメモ化用配列
bool visited[4][4][200015];
long long cache_dfs[4][4][200015];

long long dfs(long long l, long long r, long long p) {
    if (visited[l][r][p]) return cache_dfs[l][r][p];

    if (p == 1) {
        long long ret = 0;
        if (l == 0 || l == 1) {
            if (r == 0) ret = 2;
            else if (r == 1) ret = 3;
            else ret = 3;
        } else {
            if (r == 0) ret = 1;
            else if (r == 1) ret = 2;
            else ret = 2;
        }
        visited[l][r][p] = true;
        cache_dfs[l][r][p] = ret;
        return ret;
    }

    long long res = 0;
    for (long long i = 0; i < 3; i++) {
        bool ok = true;
        if (l == 2 && i == 0) {
            ok = false;
        }
        if (ok) {
            res += dfs(i, r, p - 1);
			res %= mod;
        }
    }
    dp[p * offset * offset + l * offset + r] = res;
    
    visited[l][r][p] = true;
    cache_dfs[l][r][p] = res % mod;
    return res % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;
    string S_input;
    cin >> S_input;
    
    // S=list(map(str, input())) と insert/append の再現
    vector<char> S;
    S.push_back('U');
    for (char c : S_input) {
        S.push_back(c);
    }
    S.push_back('U');

    dp[100] = 2;
    dp[101] = 3;
    dp[102] = 3;
    dp[110] = 2;
    dp[111] = 3;
    dp[112] = 3;
    dp[120] = 1;
    dp[121] = 2;
    dp[122] = 2;

    dfs(0, 0, 200010);
    dfs(0, 1, 200010);
    dfs(0, 2, 200010);

    long long ans = 1;
    long long l = -1, r = -1;
    long long idx = 0;
    map<char, long long> d;
    d['L'] = 0;
    d['U'] = 1;
    d['R'] = 2;
	for (long long i=1; i<S.size(); i++){
		if (S[idx-1]=='R' && S[idx]=='L'){
			ans=0;
		}
	}
    while (idx < S.size()) {
        if (S[idx] == '.') {
            l = d[S[idx - 1]];
            long long p = 1;
            idx += 1;
            while (idx < S.size()) {
                if (S[idx] == '.') {
                    p += 1;
                    idx += 1;
                } else {
                    r = d[S[idx]];
                    break;
                }
            }
            ans *= dp[p * offset * offset + l * offset + r];
            ans %= mod;
        } else {
            idx += 1;
        }
    }

    cout << ans % mod << "\n";
    return 0;
}
0