結果
| 問題 |
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;
}