結果
問題 |
No.3290 Encrypt Failed, but Decrypt Succeeded
|
ユーザー |
![]() |
提出日時 | 2025-10-04 19:18:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,361 bytes |
コンパイル時間 | 9,881 ms |
コンパイル使用メモリ | 334,968 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-04 19:19:06 |
合計ジャッジ時間 | 6,603 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 WA * 19 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> // #include<functional> using namespace std; using ll = long long; int main() { ll N, K; cin >> N >> K; string t; cin >> t; // DP[i番目] := i〜endのパターン数 vector<ll> DP(N+1, -1LL); DP[N] = 1LL; DP[N-1] = 1LL; for (int i=N-2;0<=i;i--) { string s1 = t.substr(i, 1); string s2 = t.substr(i, 2); int d1 = stoi(s1); int d2 = stoi(s2); if (d1 == 0) { DP[i] = 0; } else if (d2==10 || d2==20) { DP[i] = DP[i+2]; } else if (d2<=26) { DP[i] = DP[i+1] + DP[i+2]; } else { DP[i] = DP[i+1]; } } // function<ll(int)> dfs = [&](int n) { // if (-1LL<DP[n]) return DP[n]; // if (N-1<=n) { // return DP[n] = 1LL; // } // if (t[n]=='0') { // return DP[n] = 0LL; // } // string s2 = t.substr(n, 2); // int d2 = stoi(s2); // ll res = 0LL; // // この時は1/0に分けられないので特別。 // if (d2==10 || d2==20) { // res += dfs(n+2); // return DP[n] = res; // } // if (d2<=26 && n+2<=N-1) { // res += dfs(n+2); // } // res += dfs(n+1); // return DP[n] = res; // }; // dfs(0); string res = ""; ll count = 0; for (int i=0;i<N;) { string s2 = t.substr(i, i==N-1 ? 1 : 2); int d1 = stoi(t.substr(i, 1)); int d2 = stoi(s2); char v; // この時は1/0に分けられないので特別。 if (d2==10 || d2==20) { v ='a' + (d2-1); res += v; i+=2; continue; } if (d2<10) { v ='a' + (d2-1); res += v; i++; continue; } if (d2<=26) { if (count+DP[i+1]<K) { v ='a' + (d2-1); res += v; count += DP[i+1]; i +=2; } else { v ='a' + (d1-1); res += v; i++; } } else { v = 'a' + (d1-1); res += v; i++; } } cout << res << endl; }