結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
ユーザー Plan8
提出日時 2025-10-18 20:09:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 2,710 bytes
コンパイル時間 12,208 ms
コンパイル使用メモリ 402,512 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-18 20:09:53
合計ジャッジ時間 14,769 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: methods `get_all` and `dfs` are never used
  --> src/main.rs:83:8
   |
19 | impl Solver {
   | ----------- methods in this implementation
...
83 |     fn get_all(&self) -> Vec<String> {
   |        ^^^^^^^
...
91 |     fn dfs(&self, pos: usize, cur: &mut String, all: &mut Vec<String>) {
   |        ^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use proconio::input;

fn main() {
    input! {
        n: usize,
        k: u64,
        s: String,
    }
    let solver = Solver::new(n, s);
    let ans = solver.solve(k);
    println!("{}", ans);
}

struct Solver {
    n: usize,
    s: String,
}

impl Solver {
    fn new(n: usize, s: String) -> Self {
        Self { n, s }
    }

    fn solve(&self, k: u64) -> String {
        // let mut cur = "".to_string();
        // let mut all = vec![];
        // self.dfs(0, &mut cur, &mut all);
        // all.sort();
        // return all[(self.k - 1) as usize].clone();
        let mut ans = "".to_string();
        let dp = self.count();
        let mut pos = 0;
        let mut res = k;

        while pos < self.n {
            for len in 1..=2 {
                if !self.to_num_ok(pos, len) {
                    continue;
                }
                let cnt = dp[pos + len];
                if cnt < res {
                    res -= cnt;
                    continue;
                }
                ans.push(
                    self.s[pos..pos + len]
                        .parse::<u8>()
                        .map(|x| (b'a' + x - 1) as char)
                        .unwrap(),
                );
                pos += len;
                break;
            }
        }

        ans
    }

    fn count(&self) -> Vec<u64> {
        let mut dp = vec![0u64; self.n + 1];
        dp[self.n] = 1;
        for i in (0..self.n).rev() {
            for len in 1..=2 {
                if self.to_num_ok(i, len) {
                    dp[i] = dp[i].saturating_add(dp[i + len]);
                }
            }
        }
        dp
    }

    fn to_num_ok(&self, i: usize, len: usize) -> bool {
        if i + len > self.n {
            return false;
        }
        if self.s[i..i + len].starts_with('0') {
            return false;
        }
        let sub = &self.s[i..i + len];
        sub.parse::<u8>().is_ok_and(|x| (1..=26).contains(&x))
    }

    fn get_all(&self) -> Vec<String> {
        let mut cur = "".to_string();
        let mut all = vec![];
        self.dfs(0, &mut cur, &mut all);
        all.sort();
        all
    }

    fn dfs(&self, pos: usize, cur: &mut String, all: &mut Vec<String>) {
        if pos == self.n {
            all.push(cur.clone());
            return;
        }
        for len in 1..=2 {
            if self.to_num_ok(pos, len) {
                cur.push(
                    self.s[pos..pos + len]
                        .parse::<u8>()
                        .map(|x| (b'a' + x - 1) as char)
                        .unwrap(),
                );
                self.dfs(pos + len, cur, all);
                cur.pop();
            }
        }
    }
}
0