結果
| 問題 |
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 |
ソースコード
#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;
}