結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
コンテスト
ユーザー Kyutatsu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0