結果

問題 No.3753 Certainly a Cretan
コンテスト
ユーザー marc2825
提出日時 2026-08-19 00:45:47
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,713 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,106 ms
コンパイル使用メモリ 220,016 KB
実行使用メモリ 54,016 KB
最終ジャッジ日時 2026-10-02 20:56:38
合計ジャッジ時間 8,884 ms
ジャッジサーバーID
（参考情報） 		judge4_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    string S;
    cin >> S;

    vector<vector<int>> dp(N + 1);
    dp[0] = {1};

    auto calc = [&](int i, const vector<int>& prv) {
        int people = i + 1;
        vector<int> nxt(i + 2);

        for (int k = 0; k <= i; ++k) {
            if (prv[k] == 0) continue;

            {
                int liar = k;
                int honest = people - liar;

                bool answer_yes = honest * 2 > people;

                if (answer_yes == (S[i] == 'Y')) {
                    nxt[k] += prv[k];
                    if (nxt[k] >= MOD) nxt[k] -= MOD;
                }
            }

            {
                int liar = k + 1;

                bool correct_yes = liar * 2 > people;
                bool answer_yes = !correct_yes;

                if (answer_yes == (S[i] == 'Y')) {
                    nxt[k + 1] += prv[k];
                    if (nxt[k + 1] >= MOD) nxt[k + 1] -= MOD;
                }
            }
        }

        return nxt;
    };

    for (int i = 0; i < N; ++i) {
        dp[i + 1] = calc(i, dp[i]);
    }

    while (Q--) {
        int t, x;
        cin >> t >> x;

        if (t == 1) {
            int p = x - 1;

            S[p] = (S[p] == 'Y' ? 'N' : 'Y');

            for (int i = p; i < N; ++i) {
                vector<int> nxt = calc(i, dp[i]);

                if (nxt == dp[i + 1]) {
                    break;
                }

                dp[i + 1] = move(nxt);
            }
        } else {
            int K = x;
            cout << dp[N][K] << '\n';
        }
    }
}
0