【競プロ】 ABC 173 C問題を解く

Programming Competition Atcoder Nim

こんにちは、モリリンです。
今日からAtcoder Problemsでランダムに茶色レートの問題を 1 日 1 問づつ解いて、解説していこうと思います。
言語はかなり使い勝手のいいNimを使います。
記念すべき第一問目は、こちらです
解説は、なるべく競プロ初心者にもわかるようにしていきます。

問題文

$H$ 行 $W$ 列に並ぶマスからなるマス目があります。上から $i$ 行目、左から $j$ 列目 ( $1 \leq i \leq H,1\leq j\leq W$ ) のマスの色は文字 $c_{i,j}$ として与えられ、 $c_{i,j}$ が . のとき白、# のとき黒です。次の操作を行うことを考えます。行を何行か選び (0 行でもよい)、列を何列か選ぶ (0 列でもよい)。そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。正の整数 $K$ が与えられます。操作後に黒いマスがちょうど $K$ 個残るような行と列の選び方は何通りでしょうか。ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

次の操作を行うことを考えます。

行を何行か選び (0行でもよい)、列を何列か選ぶ (0列でもよい)。そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。

正の整数 $K$ が与えられます。操作後に黒いマスがちょうど $K$ 個残るような行と列の選び方は何通りでしょうか。ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

使う知識

この問題では以下の知識を使います。

Bit全探索

bit全探索は、N個の集合からいくつかのものを取り出すという操作を全て試したいときに使います。例えば、{0,1,..,N-1}という集合からいくつかものを取り出すときには、以下のように分けて考えます。
- 0 を取り出す、取り出さない
- 1 を取り出す、取り出さない
- ...
- i を取り出す、取り出さない
- ...
- N-1 を取り出す、取り出さない
これらの状態は二進数を使うと１つの数字で表せます。
方法は、{0,1,3} を 1011, {1,2,3,4,5} を 11111 のように、 $i$ を取り出す時は二進数で $i$ けた目を1にするように対応させることでできます。逆に二進数で $i$ 桁目が1の時、 $i$ を取り出している状態を表しています。そして、全ての場合を確かめるのには、変数bitを $0..2^N-1$ の値をあてて、二進数bitの $i$ 桁目が1かどうかによって、何を選んでるかがわかります。二進数bitの $i$ 桁目が1かどうかを調べるのには、bitopsというライブラリのtestBitを使います。例として、{0,1,..N-1}の部分集合を全列挙してプリントさせるコードを載せます。
```
import bitops

const N = 4

for bit in 0..<(1 shl N):
    var sub: seq[int]
    for i in 0..<N:
        if bit.testBit(i):
            sub.add(i)
    echo sub
```
計算量は $O(N2^N)$ になります。

問題のポイント

この問題のポイントは、 $H, W$ の制約が $1\leq H,W \leq6$ とかなり小さいことです。
なので、H,W についての計算量が多くなっても耐えられそうです。
そしてもう一つは、行を何行か選び、のように何かをいくつか選び、と書かれているので、bit全探索を使えば良さそうだなと気づくことです。

解き方

行を何行か選びというのは、

１行目を選ぶ、選ばない
２行目を選ぶ、選ばない
...
W行目を選ぶ、選ばない

をbit全探索で全部試せばいいということになります。
そしてそのそれぞれの場合について、

列を何列か選ぶ

つまり、

１列目を選ぶ、選ばない
２列目を選ぶ、選ばない
...
W列目を選ぶ、選ばない

をbit全探索で全部試すということになります。

そして、選ばれた列と行ではない黒いマスをカウントして、それがK個ちょうどの場合となる数を調べていきます。

計算量

計算量は、行と列の選び方を全探索して、 $c_{i,j}$ を全て見るので、計算量は $O(HW2^{H+W})$ になります。少し多い気もしますが、 $H, W$ の制約が $1\leq H,W \leq6$ なので大丈夫そうです。

コード

以下にNimで書いたコードを載せます。

import sequtils, strutils, sugar, bitops
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld", addr result)
proc nextFloat(): float = scanf("%lf", addr result)
proc nextString(): string =
  var get = false
  result = ""
  while true:
    var c = getchar()
    if int(c) > int(' '):
      get = true
      result.add(c)
    else:
      if get: break
      get = false

proc solve(H, W, K: int, C: seq[string]): int =
  for b in 0..<(1 shl H): # 行の選び方を全探索
    for c in 0..<(1 shl W): # 列の選び方を全探索
      var cur = 0
      for i in 0..<H:　
        if b.testBit(i): 
          continue
        for j in 0..<W:
          if c.testBit(j):
            continue
          if C[i][j] == '#':
            inc(cur)
      if cur == K:
        inc(result)

proc main(): void =
  var H, W, K = nextInt()
  var C: seq[string] = newSeqWith(H, "")
  for i in 0..<H:
    C[i] = nextString()
  echo solve(H, W, K, C)
  return

main()

提出結果