結果
| 問題 | No.3290 Encrypt Failed, but Decrypt Succeeded | 
| コンテスト | |
| ユーザー |  titia | 
| 提出日時 | 2025-10-08 04:39:12 | 
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) | 
| 結果 | 
                                AC
                                 
                             | 
| 実行時間 | 31 ms / 2,000 ms | 
| コード長 | 9,102 bytes | 
| コンパイル時間 | 5,382 ms | 
| コンパイル使用メモリ | 395,300 KB | 
| 実行使用メモリ | 21,328 KB | 
| 最終ジャッジ日時 | 2025-10-08 04:39:20 | 
| 合計ジャッジ時間 | 7,584 ms | 
| ジャッジサーバーID (参考情報) | judge3 / judge4 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| sample | AC * 3 | 
| other | AC * 27 | 
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>
#include <cmath>
// Nの最大値 300,000 に対応
const int MAX_DP_SIZE = 300010;
// Kの最大値 10^18 に対応するための定数
const long long K_LIMIT = 1000000000000000000LL; // 10^18
// Kを超えるデコード総数を表す値 (K + 1)。これ以上の値は K を超えるとみなす。
const long long OVERFLOW_VAL = K_LIMIT + 1;
// DPテーブルをグローバルで定義(再帰関数からアクセスするため)
std::vector<long long> DP(MAX_DP_SIZE);
std::vector<long long> DP2(MAX_DP_SIZE);
std::string X_str; // PythonのXに対応する前処理済み文字列
// calc2の前方宣言
long long calc2(int x);
/**
 * @brief X[x:]以降の文字列をデコードする方法の総数を計算します(DP/メモ化再帰)。
 * デコード総数が OVERFLOW_VAL (K+1) を超える場合は、OVERFLOW_VAL でクリップされます。
 * @param x 現在のXのインデックス
 * @return long long デコード総数
 */
long long calc(int x) {
    if (DP[x] != -1) {
        return DP[x];
    }
    // ベースケース: インデックスが末尾または末尾+1の場合(1通り)
    if (x >= X_str.length() - 1) {
        DP[x] = 1; 
        return 1;
    }
    // X[x]X[x+1] の2文字を組み合わせた文字列
    std::string two_char_str;
    two_char_str += X_str[x];
    two_char_str += X_str[x + 1];
    // Case 1: 特殊文字 ('j' or 't') が含まれる場合
    if (two_char_str.find('j') != std::string::npos || two_char_str.find('t') != std::string::npos) {
        // X[x]が特殊文字の場合、1文字として確定。次は X[x+1:] を calc(x+1) 通り
        long long ANS = calc(x + 1);
        DP[x] = ANS;
        return ANS;
    }
    // 2文字を整数に変換
    int a = 0;
    try {
        a = std::stoi(two_char_str);
    } catch (...) {
        // 変換エラーは通常発生しないはずだが、発生時は1文字デコードのみ
        long long ANS = calc(x + 1);
        DP[x] = ANS;
        return ANS;
    }
    // Case 2: 2文字デコードが可能な場合 (11-19, 21-26)
    if ((a >= 11 && a <= 19) || (a >= 21 && a <= 26)) {
        // Pythonのロジックを忠実に再現: calc(x+2)*2 + calc2(x+1)
        
        // オーバーフロー対策: K_LIMIT (10^18) を超える場合、OVERFLOW_VAL にクリップ
        long long term1 = calc(x + 2);
        
        // calc(x+2) * 2 が OVERFLOW_VAL を超えるかチェック
        if (term1 >= OVERFLOW_VAL / 2) {
            term1 = OVERFLOW_VAL;
        } else {
            term1 *= 2;
        }
        
        long long term2 = calc2(x + 1);
        long long ANS = term1;
        
        // term1 + term2 が OVERFLOW_VAL を超えるかチェック
        if (term2 >= OVERFLOW_VAL - term1) {
            ANS = OVERFLOW_VAL;
        } else {
            ANS += term2;
        }
        
        DP[x] = ANS;
        return ANS;
    } else {
        // Case 3: 1文字デコードのみが可能な場合
        long long ANS = calc(x + 1);
        DP[x] = ANS;
        return ANS;
    }
}
/**
 * @brief X[x]X[x+1]を2文字としてデコードし、残りのX[x+2:]をデコードするパターン数を計算します。
 * 総数は calc(x+2) に等しく、OVERFLOW_VAL でクリップされます。
 * @param x 現在のXのインデックス
 * @return long long X[x]X[x+1]を2文字としてデコードするパターン数
 */
long long calc2(int x) {
    if (DP2[x] != -1) {
        return DP2[x];
    }
    // ベースケース: 2文字デコード不可能
    if (x >= X_str.length() - 1) {
        DP2[x] = 0;
        return 0;
    }
    
    std::string two_char_str;
    two_char_str += X_str[x];
    two_char_str += X_str[x + 1];
    // Case 1: 特殊文字が含まれる場合。2文字デコード不可。
    if (two_char_str.find('j') != std::string::npos || two_char_str.find('t') != std::string::npos) {
        DP2[x] = 0;
        return 0;
    }
    // 2文字を整数に変換
    int a = 0;
    try {
        a = std::stoi(two_char_str);
    } catch (...) {
        DP2[x] = 0;
        return 0;
    }
    // Case 2: 2文字デコードが可能な場合 (11-19, 21-26)
    if ((a >= 11 && a <= 19) || (a >= 21 && a <= 26)) {
        // X[x]X[x+1]を2文字デコードし、残りの X[x+2:] を calc(x+2) 通り
        // calc(x+2) の結果は既に OVERFLOW_VAL でクリップされている
        long long ANS = calc(x + 2); 
        DP2[x] = ANS;
        return ANS;
    } else {
        // Case 3: 2文字デコード不可
        DP2[x] = 0;
        return 0;
    }
}
int main() {
    // 高速な入出力設定
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // Nはint (300,000) で十分
    int N;
    // Kはlong long (10^18) が必要
    long long K;
    std::string S;
    // 入力
    if (!(std::cin >> N >> K)) return 0;
    if (!(std::cin >> S)) return 0;
    // 文字列 X の生成 (前処理)
    X_str.clear();
    int ind_s = 0;
    while (ind_s < N) {
        if (ind_s + 1 < N && S[ind_s + 1] == '0') {
            // 'x0'の形を特殊文字に変換
            if (S[ind_s] == '1') {
                X_str.push_back('j'); // 10 -> j
                ind_s += 2;
            } else if (S[ind_s] == '2') {
                X_str.push_back('t'); // 20 -> t
                ind_s += 2;
            } else {
                // 30, 40などはデコードできないため、元のPythonコードのロジックに従い1文字として処理
                // 3, 4, ... を X_str に追加
                X_str.push_back(S[ind_s]);
                ind_s++;
            }
        } else {
            X_str.push_back(S[ind_s]);
            ind_s++;
        }
    }
    
    int X_len = X_str.length();
    if (X_len == 0 && N > 0) return 0;
    // N=300000に対してX_lenも最大300000程度になる
    // DPテーブルの初期化と設定
    // Nの最大値に合わせて resize/assign する
    DP.assign(X_len + 10, -1);
    DP2.assign(X_len + 10, -1);
    
    // calc(X_len) (空文字列) は1通り
    DP[X_len] = 1;
    DP2[X_len] = 0;
    // K番目の文字列の探索
    std::string ANS_str;
    long long K_temp = K;
    int ind = 0;
    
  
    while (ind < X_len) {
    if (K_temp>1){
        // バイナリサーチ: calc(mid) >= K_temp を満たす最大の mid を探す
        // OK: デコード総数 >= K_temp
        // NG: デコード総数 < K_temp
        int OK = ind;
        int NG = X_len; 
        
        while (NG > OK + 1) {
            int mid = OK + (NG - OK) / 2;
            long long score = calc(mid);
            if (score >= K_temp) {
                OK = mid;
            } else {
                NG = mid;
            }
        }
        
        // ここでの OK は X[OK]X[OK+1] を2文字デコードするグループの開始位置
        
        // X[OK]を1文字デコードするパターン群 calc(OK+1) 通りをスキップ
        if (OK + 1 <= X_len) {
            // K_temp は K_LIMIT を超えない値として保持されているので、オーバーフローの心配はない
            K_temp -= calc(OK + 1);
        } else {
             // このパスはバイナリサーチのロジック上、通らないはず
             break;
        }
        
        // X[ind]からX[OK-1]までは1文字デコードが確定
        for (int i = ind; i < OK; ++i) {
            if (X_str[i] == 'j' || X_str[i] == 't') {
                ANS_str += X_str[i];
            } else {
                ANS_str += static_cast<char>(X_str[i] - '0' + 'a' - 1);
            }
        }
        // X[OK]X[OK+1] を2文字でデコード
        std::string two_char_val;
        if (OK + 1 < X_len) {
            two_char_val += X_str[OK];
            two_char_val += X_str[OK + 1];
        } else {
             // このパスはバイナリサーチのロジック上、通らないはず
             break;
        }
        // 2文字の数字を整数に変換
        int decoded_val = 0;
        try {
            decoded_val = std::stoi(two_char_val);
        } catch (...) {
            // デコードエラーが発生した場合、処理を中断
            return 0;
        }
        // 変換してANSに追加 (例: 11 -> k)
        ANS_str += static_cast<char>(decoded_val + 'a' - 1);
        ind = OK + 2; // 次の開始インデックス
        
    }
        if (K_temp == 1) {
            // 残りの文字列を1文字ずつデコード(これがK番目のデコードパターンになる)
            for (int i = ind; i < X_len; ++i) {
                if (X_str[i] == 'j' || X_str[i] == 't') {
                    ANS_str += X_str[i];
                } else {
                    ANS_str += static_cast<char>(X_str[i] - '0' + 'a' - 1);
                }
            }
            break;
        }
    }
    
    // 結果を出力
    std::cout << ANS_str << "\n";
    return 0;
}
            
            
            
        