#1186492 (Rust) No.3685 ワロングアンサーやんけ！

• 問題: No.3685 ワロングアンサーやんけ！
• ユーザー: yiwiy9
• 提出日時: 2026-09-12 01:35:46
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 164 ms / 2,000 ms
• コード長: 3,436 bytes
• コンパイル時間: 1,313 ms
• コンパイル使用メモリ: 188,032 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-12 01:35:53
• 合計ジャッジ時間: 5,619 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 32

ソースコード

use itertools::Itertools;
use proconio::{input, marker::Chars};

/// `R` のどの補完でも、先頭 `K` 文字がすべて `A` になるか。
fn p_is_forced_true(r: &[char], k: usize) -> bool {
    r[..k].iter().all(|&c| c == 'A')
}

/// `R` のどの補完でも、`W` が一つ以上存在するか。
fn q_is_forced_true(r: &[char]) -> bool {
    r.contains(&'W')
}

/// https://yukicoder.me/problems/no/3685
/// - 何ごとの話にすると見やすい？ 何だけ持てばいい？
///   文字ごとではなく、`P = 先頭 K 文字がすべて A`、`Q = W が一つ以上ある` の二つの命題で見る。
/// - それについて、何が分かれば答えになる？
///   `R` から `P`、`Q` が必ず真かと、`S` の条件からどちらを真または偽に固定すべきかが分かればよい。
/// - 何を捨ててよく、なぜそれで足りる？ 何が効く / 何が禁止？
///   `?` の埋め方の全列挙や、個数による細かな場合分けは不要。
///   `Warong = P && Q`、`NotWarong = !P || !Q` なので、確定した命題だけ追えばよい。
/// - その情報をどう更新 / 判定 / 集計すれば実装できる？
///   `Warong` なら `P` を真にして、`Q` を真にする `W` の候補が後半に一つだけならそこも確定する。
///   `NotWarong` なら、`P` が必ず真なら `Q` を偽にし、`Q` が必ず真なら `P` を偽にする。
///   個数は最後に、その条件を満たす `?` が一つしかないかを判定するためだけに使う。
fn main() {
    input! {
        t: usize,
    }

    for _ in 0..t {
        input! {
            r: Chars,
            s: String,
            k: usize,
        }
        let p_forced_true = p_is_forced_true(&r, k);
        let q_forced_true = q_is_forced_true(&r);
        let mut ans = r.clone();

        match s.as_str() {
            "Warong" => {
                // P を真にする。
                for c in &mut ans[..k] {
                    if *c == '?' {
                        *c = 'A';
                    }
                }

                // P によって先頭はすべて A なので、W の候補は後半だけにある。
                let back_has_w = ans[k..].contains(&'W');
                let back_q_cnt = ans[k..].iter().filter(|&&c| c == '?').count();
                if !back_has_w && back_q_cnt == 1 {
                    *ans[k..].iter_mut().find(|c| **c == '?').unwrap() = 'W';
                }
            }
            "NotWarong" => {
                if p_forced_true {
                    // P が必ず真なので、NotWarong にするには Q を偽にするしかない。
                    for c in &mut ans {
                        if *c == '?' {
                            *c = 'A';
                        }
                    }
                } else if q_forced_true {
                    // Q が必ず真なので、NotWarong にするには P を偽にするしかない。
                    let front_has_w = ans[..k].contains(&'W');
                    let front_q_cnt = ans[..k].iter().filter(|&&c| c == '?').count();
                    if !front_has_w && front_q_cnt == 1 {
                        *ans[..k].iter_mut().find(|c| **c == '?').unwrap() = 'W';
                    }
                }
            }
            _ => unreachable!(),
        }

        println!("{}", ans.iter().join(""));
    }
}