深さ優先探索を使って全探索を行う AtCoder ABC 015 C

問題

C: 高橋くんのバグ探し - AtCoder Beginner Contest 015 | AtCoder

ソースコード

解説

バグを発見するためには、全ての質問に対してそれぞれ全ての選択肢をいずれかを選んだパターンを全列挙し、バグがあるか否かを判断しなければならない。

全列挙可能か

全列挙する場合、気をつけなければならないのが計算量だ。この問題ではN個の質問に対してそれぞれ、K個の選択肢が存在する。全列挙するためには0(K^N)となる。仮にNの最大値が9辺りになると解けない。しかし、今回の問題では1≦N, K≦5と小さい数字なので全列挙可能となる。

深さ優先探索を使った全探索

今回は深さ優先探索を使った全探索を行う。

深さ優先探索の作り方

整理する。

Step1 求めたい事は何かで戻り値を決定

今回の求めたいものは、選んだ選択肢の排他的論理和が0になるか否かである。つまり、真偽値を返すメソッドを作る。

Step3 どの値を「深さ」のパラメータにするか

どの値を「深さ」のパラメータにするかを決める事で大まかな関数のデザインがきまる。今回の問題では、K個の選択肢をN回行う。このNが深さのパラメータとなる。計算量でいうとO(K^N)のNにあたる。

Step3 深さが変わる度に状態が変化するものを引数にする

今回の問題では再帰する度に状態が変わるのは、以下の２つ。 `` 1. その深さの場合まで計算した排他的論理和 2. 難問といたか(N)

ここまで考慮すると boolean dfs(int xor, int depth)という関数となる。

Step4 再帰の抜ける条件を書く

深さ優先探索は再帰関数となっているので、再帰関数のデザインに則って書いていく。基本的には以下のようになる。

今回の問題では、再帰が抜けるタイミングは「深さ」が探索する深さを越した時である。よって

if (depth == N)

となる。この条件に当てはまる時は最も深い所まで行った時なので、xorも最も深い所の状態となる。つまりxorは全ての問題の排他的論理和が計算された状態ということになる。よってこの時に、求めたいものであるxor == 0を行ってあげれば良い。 これで再帰を抜ける条件を書くことができた。

Step5 全探索できるように再帰する

最後に、全探索できるように再帰の処理を書いていく。コツは、引数を今いる深さの状態から次の深さの状態に更新するイメージ。

現在の深さをdfs(int xor, int depth)とすると、それぞれの引数について次の深さは以下のように表現できる。

1. xor: 今の深さの選択肢のどれかを選び、排他的論理和と取ったもの
2. depth: 単純に深さを１つあげる

1. xor: 今の深さの選択肢のどれかを選び、排他的論理和と取ったもの

選択肢はK個存在するので全探索するためにfor文で全ての選択肢を処理するすると、その深さでの選択肢が１つ決まるので、その値と今のxorの排他的論理和を計算する。そしてその値を引数に設定してあげる。

2. depth: 単純に深さを１つあげる

これはdepth + 1でOK。

これらを踏まえて

となる。