結果

問題 No.2106 Wild Cacco
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:16:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,271 bytes
コンパイル時間 735 ms
コンパイル使用メモリ 86,092 KB
実行使用メモリ 16,068 KB
最終ジャッジ日時 2025-05-14 13:18:16
合計ジャッジ時間 5,950 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <map> // Using map for sparse DP table

using namespace std;

// Using long long for intermediate counts potentially, but map value stores int as per MOD arithmetic
using ll = long long; 

// Define the modulus
const int MOD = 998244353;

// Use map to store DP states. The key is a pair {x, y} representing the state,
// and the value is the number of ways to reach this state.
// We use two maps to alternate between current and next DP states.
map<pair<int, int>, int> dp_M[2];

int main() {
    // Faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s; // Input string
    cin >> s;
    int n = s.length(); // Length of the string

    // A correct parenthesis sequence must have an even length.
    // If N is odd, it's impossible to form one, so the answer is 0.
    if (n % 2 != 0) {
        cout << 0 << endl;
        return 0;
    }

    ll total_ans = 0; // Initialize total count of good strings

    // The core idea is based on the necessary and sufficient conditions for a string `t` containing '(', ')', '?'
    // to be a "good string":
    // 1. Length N must be even. (Checked above)
    // Let x_i be the balance of prefix t[1..i] if all '?' are treated as '('.
    // Let y_i be the balance of prefix t[1..i] if all '?' are treated as ')'.
    // 2. x_p >= 0 for all prefixes p=1..N. (Balance must not drop below 0 even if '?' are greedily '('.
    // 3. y_N <= 0. (Final balance must be non-positive if '?' are greedily ')'. Combined with x_N >= 0 (from cond 2), this ensures final balance 0 is achievable)
    // 4. y_p >= y_N for all prefixes p=1..N. (The balance path treating '?' as ')' must never drop below its final value).
    // This condition is equivalent to saying the minimum value of the y path occurs at index N.

    // To count strings satisfying these conditions, we iterate over all possible values M for the final balance y_N.
    // For a fixed M, we run a DP calculation. The DP counts paths that satisfy:
    // - x_p >= 0 for all p <= N
    // - y_p >= M for all p <= N
    // - y_N = M
    // The DP state dp[i][x][y] stores the number of ways to form prefix t[1..i] ending in state (x_i, y_i).
    // We sum the counts for states where y_N = M. Summing over all valid M gives the total answer.
    // M must be <= 0 (from condition 3). M can range from 0 down to -N.
    for (int M = 0; M >= -n; --M) {
        // Initialize DP state for the current value of M
        int current_M_idx = 0; // Index for current DP table (0 or 1)
        dp_M[current_M_idx].clear(); // Clear the map for the new M value

        // Base case: At index 0 (empty prefix), state is (x=0, y=0).
        // This state is valid only if its y value (0) is >= M. Since M <= 0, this is always true.
        dp_M[current_M_idx][{0, 0}] = 1; 

        // Dynamic Programming: Iterate through each character of the string s
        for (int i = 0; i < n; ++i) {
            int next_M_idx = 1 - current_M_idx; // Index for the next DP table
            dp_M[next_M_idx].clear(); // Clear the map for the next states

            // Iterate over all reachable states (x, y) at step i for the current M
            for (auto const& [state, count] : dp_M[current_M_idx]) {
                int x = state.first; // Current x value
                int y = state.second; // Current y value

                // If count is 0, this state doesn't contribute. Skip. (Map iteration generally handles this).
                if (count == 0) continue;

                char c = s[i]; // Character at current index i

                // Consider transitions based on the character s[i]
                // Note: '.' can be replaced by '(', ')', or '?'

                // Possibility 1: The character is '(' or '.' is replaced by '('
                if (c == '(' || c == '.') {
                    int next_x = x + 1; // x increases by 1
                    int next_y = y + 1; // y increases by 1
                    // Check validity conditions for the next state: x must be non-negative, y must be >= M
                    if (next_x >= 0 && next_y >= M) {
                         // Add the count to the next state, taking modulo
                         dp_M[next_M_idx][{next_x, next_y}] = (dp_M[next_M_idx][{next_x, next_y}] + count) % MOD;
                    }
                }
                
                // Possibility 2: The character is ')' or '.' is replaced by ')'
                 if (c == ')' || c == '.') {
                    int next_x = x - 1; // x decreases by 1
                    int next_y = y - 1; // y decreases by 1
                     // Check validity conditions
                     if (next_x >= 0 && next_y >= M) {
                         dp_M[next_M_idx][{next_x, next_y}] = (dp_M[next_M_idx][{next_x, next_y}] + count) % MOD;
                     }
                }

                // Possibility 3: The character is '?' or '.' is replaced by '?'
                 if (c == '?' || c == '.') {
                    int next_x = x + 1; // x increases by 1 (treating '?' as '(' for x path)
                    int next_y = y - 1; // y decreases by 1 (treating '?' as ')' for y path)
                     // Check validity conditions
                     if (next_x >= 0 && next_y >= M) {
                         dp_M[next_M_idx][{next_x, next_y}] = (dp_M[next_M_idx][{next_x, next_y}] + count) % MOD;
                     }
                }
            }
            // Switch to the next DP table index for the next character processing
            current_M_idx = next_M_idx;
        }
        
        // After processing all N characters:
        // Sum up the counts for final states where y_N = M.
        // These paths satisfy all conditions for a good string ending with minimum y path value M.
        for(auto const& [state, count] : dp_M[current_M_idx]) {
            int y = state.second; // Final y value
            // Check if the final y coordinate is exactly M
            if (y == M) { 
                 total_ans = (total_ans + count) % MOD; // Add count to the total answer
            }
        }
    }

    // Output the final total count modulo MOD
    cout << total_ans << endl;

    return 0;
}
0