Atcoder を始めて２回目のコンテストに出ました

このブログの概要

Atcoder を始めて２回目のコンテスト（ABC356）に出ました。

atcoder.jp

残念ながらB問題までしか解けなかったので、まずはC問題を解けるようにならねばと反省しております。

今日はC問題の復習をこのブログに書きます。

C問題はどんな問題？

以下がそのC問題です。

atcoder.jp

まずつまづいた点としてを整理すると以下の２つ

標準入力の受け取り方がわからん
問題文を理解するのに時間かかった

１番目の問題はもはや致命的すぎて、草生えましたw inputの配列のサイズが異なるタイプの問題を解いたことなかったので、どう受け取ればいいのか全くわからず困惑しましたw

２番目の問題は、そもそも１番目の問題が解決できていなかったのでほぼ諦めていたんですが、とりあえず解くことにしました。 ...が解釈がうまくできず、結局何を解答すればいいのかわからんというこれまた致命的な問題で死にましたw

ということでコンテスト終了後にこれら２つの問題を解消することを取り組みました。

書いたコード

まず最初に諸々解決して、書いたコードが以下になります。

use proconio::input;

fn main() {
    input! {
        n: usize, // n本の鍵
        m: usize, // m回の実験
        k: usize, // k本以上差し込んだときに開く
    }
    let mut input_data = Vec::<(usize, Vec<usize>, String)>::new();
    for _ in 0..m {
        input! {
            c: usize,
            a: [usize; c],
            r: String,
        }

        input_data.push((c, a, r))
    }

    // ｍ回のテストパターンが通った組み合わせの回数を数える変数
    let mut answer = 0;
    // 鍵の組み合わせパターンを回す
    for key_patern in 0..(1 << n) as usize {
        // m回の実験結果を確認する
        let mut is_ok = true;
        for (_, a, r) in &input_data {
            let mut compare_key_patern = 0;
            // テストの鍵で組み合わせバイナリを作成(ex: 101, 011)
            for key in a {
                compare_key_patern |= 1 << key - 1;
            }

            let ones_count = (compare_key_patern & key_patern).count_ones();
            if !(r == "o" && ones_count >= k as u32) && !(r == "x" && ones_count < k as u32) {
                is_ok = false;
            }
        }

        // テストを満たすパターンが存在した場合にカウント
        if is_ok {
            answer += 1;
        }
    }

    println!("{}", answer);
}

標準入力の受け取り方がわからんかった問題の解決

問題のinputに以下のようなサンプルがありました。最後の行を見ていただくと他のinputと配列の数が異なります。経験値が浅い僕は「えっ、これどう受け取るの？」ってなって焦りましたw

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

というのもこの入力値を１回で全て受け取らなければならないという固定概念を持っていたせいでできませんでした。

    for _ in 0..m {
        input! {
            c: usize,
            a: [usize; c],
            r: String,
        }

        input_data.push((c, a, r))
    }

こんな感じに、回数分forで回して受け取るということを知ったので今回のコンテストを受けて良かったと思いました。めっちゃ初心者感丸出しで恥ずかしい限りなんですが、学びに関して初心に戻れて良かったです。

問題文を理解できなかった問題の解決

ここに関してはやっぱり問題を解いている量が圧倒的に足りないからと思いました。問題に関しては実際にサイトから読んでいただければと。

この問題は、ダミーの鍵と本物の鍵の２種類あって、その組み合わせによってドアが開く開かないが決定するというものです。いくつか鍵を選んでテストした結果が入力となります。

与えられたテスト結果から考えられる鍵の組み合わせは何個ですか？というのが問題のポイントでした。

ここに至るまで何回も読みましたw 本当に自分の国語力の無さに脱帽ですよ。

さて、問題に戻りますと

手元にはテスト結果しかないため、ダミーの鍵と本物の鍵の組み合わせがわかりません。なので、その二種類の鍵をつかった組み合わせをまず作ります。もし鍵が３つだったとして、組み合わせとしては以下になります。組み合わせは2³個になります。

No	鍵3	鍵2	鍵1
1	X	X	X
2	X	X	O
3	X	O	X
4	X	O	O
5	O	X	X
6	O	X	O
7	O	O	X
8	O	O	O

OとXで表現していますが、これって０と１に置き換えられますよね？そうなるとbitでの表現ができるようになります。

No	鍵3	鍵2	鍵1
1	0	0	0
2	0	0	1
3	0	1	0
4	0	1	1
5	1	0	0
6	1	0	1
7	1	1	0
8	1	1	1

これで準備は整いました。

あとは与えられたテストケースの情報とこの組み合わせを照らし合わせて、一致する組み合わせがあるか全探索します。

といっても僕は例え話がないと理解できない系の人間なので、例を書こうと思います。

たとえば問題が以下とします。

２個以上の正しい鍵をいれると開く扉である
テストケースが「鍵１、鍵２、鍵３をつかったら扉は開いた」

この場合、先ほど作成した0と1の表でテストケースの条件を満たす組み合わせは何がありますか？

No1のすべての鍵がダミーの場合、テストケースは満たせません。

No2の鍵１だけ本物の場合、テストケースは満たせません。

という感じで、No1からNo8までの組み合わせを見ていきます。

するとNo.4の011はどうでしょうか？

鍵３がダミーで、鍵１と鍵２は本物というケースの場合、テストケースは通るでしょうか？

鍵１（本物）、鍵２（本物）、鍵３（ダミー）をつかった。正しい鍵を２個以上つかっているので扉は開くはずです。ということでテストケースを満たします。

という感じで、この場合はNo4, 6, 7, 8がテストを満たしそうですね。なので、この例の場合の答えは「４」です。

こういうbitの組み合わせを全探索するやつをbit全探索っていうらしいです。調べてみるとわんさかでてくるので調べてみてください。ChatGPTのほうが楽かもですがｗ

感想

いつもC問題ぐらいから悩ましい状態なので、毎回こんな感じで復習しながら一つ一つ丁寧に問題を解いていこうと思います。

ゆじの独り言

いろいろ書きます