結果
問題 | No.1646 Avoid Palindrome |
ユーザー | monnu |
提出日時 | 2021-08-19 23:01:43 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,660 bytes |
コンパイル時間 | 4,068 ms |
コンパイル使用メモリ | 229,888 KB |
実行使用メモリ | 320,384 KB |
最終ジャッジ日時 | 2024-04-26 03:57:06 |
合計ジャッジ時間 | 83,727 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 1,863 ms
302,080 KB |
testcase_05 | AC | 1,868 ms
301,824 KB |
testcase_06 | AC | 1,794 ms
291,712 KB |
testcase_07 | AC | 1,858 ms
301,824 KB |
testcase_08 | AC | 1,862 ms
304,768 KB |
testcase_09 | AC | 1,771 ms
289,920 KB |
testcase_10 | AC | 1,812 ms
296,960 KB |
testcase_11 | AC | 1,777 ms
288,896 KB |
testcase_12 | AC | 1,862 ms
301,312 KB |
testcase_13 | AC | 1,887 ms
304,640 KB |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | AC | 924 ms
320,256 KB |
testcase_30 | AC | 919 ms
320,256 KB |
testcase_31 | AC | 920 ms
320,384 KB |
testcase_32 | AC | 930 ms
320,128 KB |
testcase_33 | AC | 931 ms
320,256 KB |
testcase_34 | TLE | - |
testcase_35 | AC | 2 ms
6,944 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,940 KB |
testcase_38 | AC | 2 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,944 KB |
testcase_40 | AC | 2 ms
6,944 KB |
testcase_41 | AC | 1 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 926 ms
320,256 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 2000000 #define MOD 998244353 #define INF 1000000000 int main(){ int N; string S; cin>>N>>S; if(N==1){ if(S[0]=='?'){ cout<<26<<'\n'; }else{ cout<<1<<'\n'; } return 0; } vector<vector<vector<ll>>> dp(N,vector<vector<ll>>(26,vector<ll>(26,0))); if(S[0]=='?'&&S[1]=='?'){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k){ continue; } dp[1][j][k]=1; } } }else if(S[0]=='?'){ for(int j=0;j<26;j++){ if(j==S[1]-'a'){ continue; } dp[1][j][S[1]-'a']=1; } }else if(S[1]=='?'){ for(int k=0;k<26;k++){ if(S[0]-'a'==k){ continue; } dp[1][S[0]-'a'][k]=1; } }else{ if(S[0]!=S[1]){ dp[1][S[0]-'a'][S[1]-'a']=1; } } for(int i=2;i<N;i++){ if(S[i]!='?'){ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ if(j==k||S[i]-'a'==j||S[i]-'a'==k){ continue; } dp[i][k][S[i]-'a']+=dp[i-1][j][k]; dp[i][k][S[i]-'a']%=MOD; } } }else{ for(int j=0;j<26;j++){ for(int k=0;k<26;k++){ for(int l=0;l<26;l++){ if(j==k||k==l||l==j){ 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++){ ans+=dp[N-1][j][k]; ans%=MOD; } } cout<<ans<<'\n'; }