【Rust】ABC441感想（A~C）

AtCoder Beginner Contest 441

unrated参加しまして、ABC3完でした。
今回はA~Cの感想を書きます。

A - Black Square

$P \in [X, X+100)$かつ$Q \in [Y, Y+100)$のとき、$(P,Q)$は黒く塗られています。
わざわざマス目を用意する必要がないというところは面白いですね。

fn main() {
    input! {
        p: usize,
        q: usize,
        x: usize,
        y: usize,
    }

    if (x >= p && x < p + 100) && (y >= q && y < q + 100) {
        pr("Yes");
    } else {
        pr("No")
    }
}

B - Two Languages

$w_i$が高橋語か青木語かは、
$w_i$内の文字$w_{i,j}$をくまなく確認し、

• 高橋語で使われていない文字が存在する場合、青木語
• 青木語で使われていない文字が存在する場合、高橋語
• 上記のような文字が全く存在しない場合、不明

のようにして判定することができます。

fn main() {
    input! {
        n: usize,
        m: usize,
        s: Chars,
        t: Chars,
        q: usize,
        w: [Chars; q],
    }

    let mut t_set: HashSet<char> = HashSet::new();
    for &c in &s {
        t_set.insert(c);
    }
    
    let mut a_set: HashSet<char> = HashSet::new();
    for &c in &t {
        a_set.insert(c);
    }

    let mut ans = vec![];
    for i in 0..q {
        let mut f = 0;
        for &c in &w[i] {
            if !t_set.contains(&c) {
                f = 2;
            }
            if !a_set.contains(&&c) {
                f = 1;
            }

            if f != 0 {
                break;
            }
        }
        if f == 2 {
            ans.push("Aoki");
        }else if f == 1 {
            ans.push("Takahashi")
        }else {
            ans.push("Unknown");
        }
    }
    pr(ans.iter().join("\n"));
}

C - Sake or Water

この問題は論理的思考力が高い人にとっては余裕なのでしょうが、私はだいぶ沼にハマってしまいました。
というのは、カップそれぞれの液体の量がわかっているので、高橋くんはいくつかの瓶をランダムに選ぶのではなく、なるべく大きい方から選ぶという戦略を取れるからです。

つまり、選ばれなかったカップの方にほとんど日本酒が含まれていたとしても、カップの容量が小さいので影響が低いということですね。

この戦略をとった時の最悪ケースが大きい順に$N-K$個のカップの中に水、それ以降のカップの中に日本酒が存在する場合ですから、$N-K+1$番目から大きい順にカップを選択してはじめて合計で$X$ml以上になったときの個数が答えとなります。$N$番目まで見ても合計が$X$ml以上とならなければ-1を出力します。

以上で、ソートがボトルネックとなり$O(NlogN)$でこの問題を解くことができました。

fn main() {
    input! {
        n: usize,
        k: usize,
        x: usize,
        a: [usize; n],
    }

    let mut ans = n - k;
    let mut sum = 0;
    let sorted = a.iter().cloned().sorted().rev().collect::<Vec<usize>>();
    for i in n - k..n {
        ans += 1;
        sum += sorted[i];
        if sum >= x {
            break;
        }
    }
    if sum < x {
        pr("-1");
    } else {
        pr(ans);
    }
}

まとめ

C問題ですが、バーチャルコンテスト後にChatGPT 5.2 CodexやSonnet4.5に投げても正解することができませんでした。
このような問題はAIが苦手とする分野なのでしょうか。
これを見ると、まだまだAIに実装を丸投げするのは怖いなと思う次第でした。