このブログの概要
Atcoder を始めて2回目のコンテスト(ABC356)に出ました。
atcoder.jp
残念ながらB問題までしか解けなかったので、まずはC問題を解けるようにならねばと反省しております。
今日はC問題の復習をこのブログに書きます。
C問題はどんな問題?
以下がそのC問題です。
atcoder.jp
まずつまづいた点としてを整理すると以下の2つ
- 標準入力の受け取り方がわからん
- 問題文を理解するのに時間かかった
1番目の問題はもはや致命的すぎて、草生えましたw
inputの配列のサイズが異なるタイプの問題を解いたことなかったので、どう受け取ればいいのか全くわからず困惑しましたw
2番目の問題は、そもそも1番目の問題が解決できていなかったのでほぼ諦めていたんですが、とりあえず解くことにしました。
...が解釈がうまくできず、結局何を解答すればいいのかわからんというこれまた致命的な問題で死にましたw
ということでコンテスト終了後にこれら2つの問題を解消することを取り組みました。
書いたコード
まず最初に諸々解決して、書いたコードが以下になります。
use proconio::input;
fn main() {
input! {
n: usize,
m: usize,
k: usize,
}
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 {
let mut is_ok = true;
for (_, a, r) in &input_data {
let mut compare_key_patern = 0;
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
というのもこの入力値を1回で全て受け取らなければならないという固定概念を持っていたせいでできませんでした。
for _ in 0..m {
input! {
c: usize,
a: [usize; c],
r: String,
}
input_data.push((c, a, r))
}
こんな感じに、回数分forで回して受け取るということを知ったので今回のコンテストを受けて良かったと思いました。
めっちゃ初心者感丸出しで恥ずかしい限りなんですが、学びに関して初心に戻れて良かったです。
問題文を理解できなかった問題の解決
ここに関してはやっぱり問題を解いている量が圧倒的に足りないからと思いました。
問題に関しては実際にサイトから読んでいただければと。
この問題は、ダミーの鍵と本物の鍵の2種類あって、その組み合わせによってドアが開く開かないが決定するというものです。
いくつか鍵を選んでテストした結果が入力となります。
与えられたテスト結果から考えられる鍵の組み合わせは何個ですか?
というのが問題のポイントでした。
ここに至るまで何回も読みましたw
本当に自分の国語力の無さに脱帽ですよ。
さて、問題に戻りますと
手元にはテスト結果しかないため、ダミーの鍵と本物の鍵の組み合わせがわかりません。なので、その二種類の鍵をつかった組み合わせをまず作ります。
もし鍵が3つだったとして、組み合わせとしては以下になります。
組み合わせは23個になります。
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で表現していますが、これって0と1に置き換えられますよね?
そうなると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 |
これで準備は整いました。
あとは与えられたテストケースの情報とこの組み合わせを照らし合わせて、一致する組み合わせがあるか全探索します。
といっても僕は例え話がないと理解できない系の人間なので、例を書こうと思います。
たとえば問題が以下とします。
- 2個以上の正しい鍵をいれると開く扉である
- テストケースが「鍵1、鍵2、鍵3をつかったら扉は開いた」
この場合、先ほど作成した0と1の表でテストケースの条件を満たす組み合わせは何がありますか?
No1のすべての鍵がダミーの場合、テストケースは満たせません。
No2の鍵1だけ本物の場合、テストケースは満たせません。
という感じで、No1からNo8までの組み合わせを見ていきます。
するとNo.4の011はどうでしょうか?
鍵3がダミーで、鍵1と鍵2は本物というケースの場合、テストケースは通るでしょうか?
鍵1(本物)、鍵2(本物)、鍵3(ダミー)をつかった。正しい鍵を2個以上つかっているので扉は開くはずです。ということでテストケースを満たします。
という感じで、この場合はNo4, 6, 7, 8がテストを満たしそうですね。
なので、この例の場合の答えは「4」です。
こういうbitの組み合わせを全探索するやつをbit全探索っていうらしいです。調べてみるとわんさかでてくるので調べてみてください。ChatGPTのほうが楽かもですがw
感想
いつもC問題ぐらいから悩ましい状態なので、毎回こんな感じで復習しながら一つ一つ丁寧に問題を解いていこうと思います。