結果

問題 No.3753 Certainly a Cretan
コンテスト
ユーザー marc2825
提出日時 2026-08-19 00:43:00
言語 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,700 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,052 ms
コンパイル使用メモリ 214,664 KB
実行使用メモリ 9,872 KB
最終ジャッジ日時 2026-10-02 20:56:40
合計ジャッジ時間 13,302 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

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;

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

        if (t == 1) {
            int i = x - 1;
            S[i] = (S[i] == 'Y' ? 'N' : 'Y');
        } else {
            int K = x;

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

            for (int i = 0; i < N; ++i) {
                vector<int> ndp(N + 1);

                int people = i + 1;

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

                    // 人 i+1 を正直者にする
                    {
                        int liar = k;
                        int honest = people - liar;

                        bool answer_yes = honest * 2 > people;

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

                    // 人 i+1 を嘘つきにする
                    {
                        int liar = k + 1;

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

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

                dp.swap(ndp);
            }

            cout << dp[K] << '\n';
        }
    }
}
0