結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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