結果
問題 | No.1646 Avoid Palindrome |
ユーザー | HIcoder |
提出日時 | 2023-07-22 18:08:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,790 bytes |
コンパイル時間 | 1,302 ms |
コンパイル使用メモリ | 109,568 KB |
実行使用メモリ | 320,196 KB |
最終ジャッジ日時 | 2023-10-24 00:41:01 |
合計ジャッジ時間 | 89,586 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 3 ms
4,348 KB |
testcase_04 | AC | 2,567 ms
301,964 KB |
testcase_05 | AC | 2,568 ms
301,964 KB |
testcase_06 | AC | 2,471 ms
291,668 KB |
testcase_07 | AC | 2,563 ms
301,964 KB |
testcase_08 | AC | 2,577 ms
304,868 KB |
testcase_09 | AC | 2,552 ms
289,820 KB |
testcase_10 | AC | 2,512 ms
296,948 KB |
testcase_11 | AC | 2,442 ms
288,764 KB |
testcase_12 | AC | 2,559 ms
301,436 KB |
testcase_13 | AC | 2,581 ms
304,868 KB |
testcase_14 | AC | 2,705 ms
296,156 KB |
testcase_15 | AC | 2,762 ms
301,964 KB |
testcase_16 | AC | 2,684 ms
294,308 KB |
testcase_17 | AC | 2,809 ms
307,244 KB |
testcase_18 | AC | 2,728 ms
299,060 KB |
testcase_19 | AC | 2,718 ms
297,476 KB |
testcase_20 | AC | 2,743 ms
299,852 KB |
testcase_21 | AC | 2,801 ms
306,980 KB |
testcase_22 | AC | 2,707 ms
296,420 KB |
testcase_23 | AC | 2,814 ms
308,564 KB |
testcase_24 | TLE | - |
testcase_25 | AC | 2,920 ms
320,180 KB |
testcase_26 | AC | 2,924 ms
320,180 KB |
testcase_27 | AC | 2,923 ms
320,180 KB |
testcase_28 | AC | 2,932 ms
320,180 KB |
testcase_29 | AC | 2,492 ms
320,180 KB |
testcase_30 | AC | 2,492 ms
320,180 KB |
testcase_31 | AC | 2,489 ms
320,180 KB |
testcase_32 | AC | 2,494 ms
320,180 KB |
testcase_33 | AC | 2,495 ms
320,180 KB |
testcase_34 | AC | 2,921 ms
320,180 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 2 ms
4,348 KB |
testcase_38 | AC | 3 ms
4,348 KB |
testcase_39 | AC | 2 ms
4,348 KB |
testcase_40 | AC | 2 ms
4,348 KB |
testcase_41 | AC | 2 ms
4,348 KB |
testcase_42 | AC | 2 ms
4,348 KB |
testcase_43 | AC | 2,491 ms
320,180 KB |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<stack> #include<numeric> #include<queue> #include<cmath> #include<deque> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<int,int> P; typedef pair<ll,P> PP; const ll MOD=998244353; int main(){ int N; cin>>N; string S; cin>>S; /* dp[i][j][k]=i文字目がk, i-1文字目がj */ vector dp(N+1,vector<vector<ll>>(26,vector<ll>(26,0))); for(int j=0;j<26;j++){ if( !(S[0]-'a' == j || S[0]=='?') )continue; for(int k=0;k<26;k++){ if( !(S[1]-'a'==k || S[1]=='?') || k==j ) continue; dp[1][j][k]=1; } } for(int i=2;i<N;i++){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k) continue; for(int l=0;l<26;l++){ // j,k,l となっている. i文字目がl文字目 if(l==k || l==j) continue; if(!(S[i]-'a'==l || S[i]=='?')){ continue; } dp[i][k][l]+=dp[i-1][j][k]; dp[i][k][l]%=MOD; } } } } ll ans=0; for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k) continue; ans+=dp[N-1][j][k]; ans%=MOD; } } cout<<ans<<endl; /* for(int i=0;i<26;i++){ for(int j=0;j<26;j++){ if(i!=j){ dp[0][i][j]=1; } } } S=S+ (S.back()-'a'+1)%26 for(int i=0;i<N;i++){ if(S[i]!='?'){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k) continue; if(k==(S[i]-'a'))continue; //k==S[i]となるとまずい if(j==(S[i]-'a'))continue; //j==S[i]となるとまずい dp[i+1][k][S[i]-'a']+=dp[i][j][k]; } } }else{ //S[i]=='?' for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ for(int l=0;l<26;l++){ if(j==k) continue; if(j==l) continue; if(k==l) continue; dp[i+1][k][l]+=dp[i][j][k]; } } } } } for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ cout<<"dp["<<j<<"]["<<k<<"]="<<dp[N][j][k]<<endl; } } if(N>=2){ ll ans=dp[N][S[S.size()-2]-'a'][S[S.size()-1]-'a']; cout<<ans<<endl; } */ }