結果
問題 | No.2373 wa, wo, n |
ユーザー |
|
提出日時 | 2023-06-10 20:32:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,469 bytes |
コンパイル時間 | 1,659 ms |
コンパイル使用メモリ | 174,376 KB |
実行使用メモリ | 17,600 KB |
最終ジャッジ日時 | 2024-07-02 11:25:06 |
合計ジャッジ時間 | 4,074 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)int mx = 200000; // 2*(10^5) 制約のチェック用int main(){int N;cin >> N;string S;cin >> S;//制約のチェック始assert(1<=N && N<=mx); // Nの制約assert((int)S.size()==N); // |S|==Nの制約for(int i = 0; i<N; i++){bool ok = false;char c = S[i];if('a'<=c && c<='z') ok = true;if(c=='?') ok = true;assert(ok); // Sの各文字が英小文字と'?'のみからなる制約}//制約のチェック終vector<vector<bool>> dp(N+1, vector<bool>(26, false));dp[0]['n'-'a'] = true;rep(i,N) rep(j,26) if(dp[i][j]){if(j=='w'-'a'){if(S[i]=='a') dp[i+1]['a'-'a'] = true;if(S[i]=='o') dp[i+1]['o'-'a'] = true;if(S[i]=='?'){dp[i+1]['a'-'a'] = true;dp[i+1]['o'-'a'] = true;}}else{if(S[i]=='w') dp[i+1]['w'-'a'] = true;if(S[i]=='n') dp[i+1]['n'-'a'] = true;if(S[i]=='?'){dp[i+1]['w'-'a'] = true;dp[i+1]['n'-'a'] = true;}}}bool ans = false;if(dp[N]['a'-'a']) ans = true;if(dp[N]['o'-'a']) ans = true;if(dp[N]['n'-'a']) ans = true;if(ans) cout << "Yes" << endl;else cout << "No" << endl;}