結果

問題 No.3299 K-th MMA String
コンテスト
ユーザー QiToY
提出日時 2025-10-05 14:57:36
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,608 bytes
コンパイル時間 12,126 ms
コンパイル使用メモリ 398,616 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2025-10-05 14:57:55
合計ジャッジ時間 18,147 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]

fn main() {
    input! {
        n: usize, mut k: Usize1,
    }
    // M -> 1, A -> 0
    let mut dp = mvec![0usize; (n+1, 1<<2)];
    dp[n][3] += 1;
    for i in (0..n).rev() {
        for s in 0..1 << 2 {
            for c in 0..2 {
                if c == 1 && s == 2 {
                    continue;
                }
                let w = dp[i + 1][s];
                let v = &mut dp[i][(c << 1) | (s >> 1)];
                *v = (*v).saturating_add(w);
            }
        }
    }
    for i in 0..n - 2 {
        let p = 1 << (n - i - 2);
        for v in &mut dp[i] {
            *v = p - *v;
        }
    }
    eprintln!("{dp:?}");
    let mut ans = String::new();
    let mut ps = 0;
    for i in (0..n - 2).step_by(2) {
        eprintln!("{i} {ps} {k}");
        let mut ok = vec![false; 4];
        if ps == 1 {
            dp[i][2] = 1 << (n - i - 1);
            ok[2] = true;
        }
        if ps == 3 {
            dp[i][0] = 1 << (n - i - 1);
            dp[i][1] = 1 << (n - i - 1);
            ok[0] = true;
            ok[1] = true;
        }
        for s in 0..4 {
            if k < dp[i][s] {
                if ok[s] {
                    for i in i..n {
                        ans.push(if k >> (n - i - 1) & 1 == 1 { 'M' } else { 'A' });
                    }
                    println!("{ans}");
                    return;
                } else {
                    ps = s;
                    ans.push(if s & 1 == 1 { 'M' } else { 'A' });
                    ans.push(if s >> 1 == 1 { 'M' } else { 'A' });
                    break;
                }
            } else {
                k -= dp[i][s];
            }
        }
    }
    for i in (n - 1) / 2 * 2..n {
        ans.push(if k >> (n - i - 1) & 1 == 1 { 'M' } else { 'A' });
    }
    println!("{ans}");
}

/*
0 [0, 0, 0, 1]
=> MM + 0 => MMA
2 [0, 1, 0, 3], [0, 0, 0, 1]
=> MM + 1 => MMAM
*/

use proconio::{input, marker::*};
use std::{cmp::Reverse, collections::*};

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a < tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {{
        let tmp = $b;
        if $a > tmp {
            $a = tmp;
            true
        } else {
            false
        }
    }};
}

#[macro_export]
/// mvec![]
macro_rules! mvec {
    ($val:expr; ()) => {
        $val
    };
    ($val:expr; ($size:expr $(,$rest:expr)*)) => {
        vec![mvec![$val; ($($rest),*)]; $size]
    };
}
0