Pythonで解くAtCoder(ABC173:C)
こんにちは、クルトンです！
この記事では
問題のリンクを載せておきます。
この問題を解くのに必要な知識
- 計算量
- ビット全探索
方針の立て方
まず制約を見てみましょう。
- 1 ≤ H, W ≤ 6
- 1 ≤ K ≤ HW
- ci,jは'.'または'#'
このときにH, Wがとても小さいことに気づくと思います。
この程度の行数と列数なら、ありえる行と列の選び方を全パターン調べても間に合うのではないでしょうか？
なのでここからは、ありえる行と列の選び方を全パターン調べるのにかかる計算量を調べます。
まず、行の選び方が何通りか調べます。
1行目は選ぶか選ばないかの2通り。
2行目も選ぶか選ばないかの2通り。
...
H行目も選ぶか選ばないかの2通り。
2行目も選ぶか選ばないかの2通り。
...
H行目も選ぶか選ばないかの2通り。
以上から行の選び方は2^H通りあることが分かります。
同様にして列の選び方は2^W通りになります。
以上から、求める計算量は
O(2^H × 2^W) = O(2^(H+W))
となります。
このとき、制約から
2^(H+W) ≤ 4096
であり十分間に合うことが分かります。
解法
ありえる行と列の選び方を全パターン調べればよいことが分かりました。
では、どのようにすれば、全パターンを調べるプログラムが書けるでしょうか？
このような、「ある集合からいくつかの要素を選んだもの（部分集合）を全パターンについて調べる」ような問題にはビット全探索を用います。
以下にサンプルコードを載せておきます
サンプルコード
まとめ
今回は
- ビット全探索を使う
という問題でした。
ビット全探索は慣れるまでは実装が難しいので、C問題としてはわりとハードな問題だったと思います。
ではまたお会いしましょう！さようなら～
