結果
| 問題 |
No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,572 bytes |
| コンパイル時間 | 857 ms |
| コンパイル使用メモリ | 78,876 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:35 |
| 合計ジャッジ時間 | 1,991 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 WA * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// Use -1 to represent an impossible state, since the number of "pon" insertions (k1) must be non-negative.
const int INF = -1;
int main() {
// Use fast I/O for potentially large inputs
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; // Length of the final string S
cin >> n;
string s; // The final string S
cin >> s;
string t = "ponpon"; // The initial string which we need to reach by reverse operations
int m = t.length(); // Length of "ponpon", which is 6
// DP state definition:
// dp[i][j] stores the maximum possible count k1 (number of type 1 operations, i.e., "pon" insertions)
// such that the prefix of the given string S of length i (S[0...i-1]) can be reduced
// to the prefix of the target string T ("ponpon") of length j (T[0...j-1]).
// The reduction process involves two types of reverse operations:
// 1'. Deleting a "pon" substring (corresponds to k1 "pon" insertions).
// 2'. Deleting a single character 'p', 'o', or 'n' (corresponds to k2 single character insertions).
// The state dp[i][j] = k1 implicitly means that k2 single character deletions were also performed, where k2 must satisfy:
// k2 = i - j - 3*k1. Crucially, k2 must be non-negative (k2 >= 0).
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
// Base case:
// An empty prefix of S (length i=0) can be reduced to an empty prefix of T (length j=0).
// This requires k1=0 "pon" deletions and k2=0 single character deletions.
// Check validity: k2 = 0 - 0 - 3*0 = 0. Since k2 >= 0, this state is valid.
dp[0][0] = 0;
// Fill the DP table iteratively
for (int i = 1; i <= n; ++i) { // Iterate through all possible prefix lengths of S
for (int j = 0; j <= m; ++j) { // Iterate through all possible prefix lengths of T ("ponpon")
// Current state we are trying to compute is dp[i][j].
// We consider transitions from previously computed states.
// Possibility 1: The last character S[i-1] is deleted as a single character.
// This operation corresponds to reversing a type 2 insertion ('p', 'o', or 'n').
// The state dp[i][j] can be reached from dp[i-1][j].
if (dp[i - 1][j] != INF) { // Check if the state dp[i-1][j] is reachable
int prev_k1 = dp[i - 1][j]; // k1 count from the previous state
// Check if the previous state dp[i-1][j] was valid, i.e., its implied k2_prev >= 0.
// k2_prev = (i-1) - j - 3*prev_k1
if ((i - 1) - j >= 3 * prev_k1) {
// If previous state was valid, consider transitioning to dp[i][j].
// For this transition, k1 remains the same (prev_k1).
// The implied k2 for the current state dp[i][j] is k2_current = i - j - 3*prev_k1.
// Check if this k2_current is non-negative.
if (i - j >= 3 * prev_k1) {
// If valid, update dp[i][j] with the maximum k1 seen so far for this state.
dp[i][j] = max(dp[i][j], prev_k1);
}
}
}
// Possibility 2: The last character S[i-1] matches the last character T[j-1].
// This means S[i-1] is part of the target "ponpon" structure. No deletion needed for this character.
// The state dp[i][j] can be reached from dp[i-1][j-1].
if (j > 0 && s[i - 1] == t[j - 1]) { // Check bounds (j>0) and character match
if (dp[i - 1][j - 1] != INF) { // Check if the state dp[i-1][j-1] is reachable
int prev_k1 = dp[i - 1][j - 1]; // k1 count from the previous state
// Check validity of previous state: k2_prev >= 0.
// k2_prev = (i-1) - (j-1) - 3*prev_k1
if ((i - 1) - (j - 1) >= 3 * prev_k1) {
// For state dp[i][j], k1 remains prev_k1. k2 also effectively remains same (k2_prev).
// The implied k2 for the current state dp[i][j] is k2_current = i - j - 3*prev_k1.
// Check if this k2_current is non-negative.
if (i - j >= 3 * prev_k1) {
dp[i][j] = max(dp[i][j], prev_k1);
}
}
}
}
// Possibility 3: The last three characters of S ending at index i-1 (S[i-3...i-1]) form the substring "pon".
// This corresponds to reversing a type 1 insertion ("pon"). We delete this "pon" substring.
// The state dp[i][j] can be reached from dp[i-3][j].
if (i >= 3) { // Need at least 3 characters in the S prefix to check for "pon"
// Check if S[i-3...i-1] is indeed "pon"
if (s[i - 3] == 'p' && s[i - 2] == 'o' && s[i - 1] == 'n') {
if (dp[i - 3][j] != INF) { // Check if the state dp[i-3][j] is reachable
int prev_k1 = dp[i - 3][j]; // k1 count from the previous state
// Check validity of previous state: k2_prev >= 0.
// k2_prev = (i-3) - j - 3*prev_k1
if ((i - 3) - j >= 3 * prev_k1) {
// For state dp[i][j], k1 increases by 1 (current_k1 = prev_k1 + 1).
int current_k1 = prev_k1 + 1;
// k2 effectively remains the same (k2_prev).
// The implied k2 for the current state dp[i][j] is k2_current = i - j - 3*current_k1.
// Check if this k2_current is non-negative.
if (i - j >= 3 * current_k1) {
dp[i][j] = max(dp[i][j], current_k1);
}
}
}
}
}
}
}
// After filling the DP table, the answer is the maximum k1 stored in dp[n][m].
// This state corresponds to reducing the full string S (length n) to the full target string T="ponpon" (length m=6).
// If dp[n][m] is still INF (-1), it means it's impossible to perform the reduction under the problem constraints.
int final_k1 = dp[n][m];
cout << final_k1 << endl; // Output the result, which is either the max k1 or -1.
return 0;
}