💨

ABC173 C - H and Vのメモ

2022/12/10に公開

AtCoder

競プロ

bit全探索

tech

目についたC問題を解いてみるの回です。
解けたけど時間かかりました。

考察

こういういくつか選ぶ（実際いくつかは決まっていない）問題は、制約が小さければbit全探索、制約が大きければDPで解くみたいなイメージがあります。
今回は制約が小さいのでbit全探索でよさそうです。

行と列のそれぞれを選ぶ必要があるので厄介ですが、とりあえずまずは行だけで考えてみます。
黒いマスの数の数え方は置いておいて、一旦列挙することだけを考えます。

各行については、選ぶか選ばないかの2つの状態がありますので、行1つにつき2通りです。それがH行あるので $2^H$ 通りです。これは素直にbit全探索で列挙できます。Hは最大だと6で64通りです。

列についても同様に、それ単体でみれば $2^W$ 通り（最大64通り）をbit全探索で列挙できます。
ただ、実際には行と列それぞれを選ぶので、かけ合わせになります。行の状態1つにつき列の状態が $2^W$ 通りなので、全体としては掛け算で4096通りです。計算量としては全然問題ないので、実装時に混乱しなければ大丈夫です。（混乱しましたが…）

これで選ぶ行と列を列挙できます。あとは黒いマスの数え方ですが、制約が小さいのでマスの状態を二次元配列で保持して管理すればいいでしょう。選んだ行と列を赤く塗る操作をシミュレーションして # 以外の値で埋めて、終わった後に二次元配列を走査して # を数えてKと一致するかどうかを見ればいいでしょう。

実装

提出コードにコメントを追加したものです。

bit全探索はビット列の列挙のためのループと、個別のビット列について各桁を走査してビットが立っているか調べるためのループの二重ループになります。
掛け合わせる場合はさらにループがネストします。行のためのループのうちのどこに列のためのループを入れるか要注意です。行を塗り終わった後に列の列挙をしたいので、行の二重ループのうちの2つ目のループが終わった後に列のbit全探索の処理を入れます。
（ここを間違えてバグらせてました…）

あとはマス目の状態を表す二次元配列はループのたびにリセットが必要なのでコピーするということ、列の列挙のたびに二次元配列はリセットするが初期状態へのリセットではなく行は塗られた状態へのリセットになることなどが注意点でしょうか。

fun main() {
    val (h, w, k) = readLine()!!.split(" ").map { it.toInt() }
    val template = Array(h) {
        readLine()!!.toCharArray()
    }

    var ans = 0

    // 行の選択状態を表すビット列の列挙
    for(hBit in 0 until  (1 shl h)) {
        // マス目（書き換えるので都度コピーする）
        var square = template.map { it.clone() }

        // ビット列を走査して各桁のビットが立っているか判定
        for(i in 0 until h) {
            if(hBit and (1 shl i) != 0) {
                // ビットが立っていたらその行を赤く塗る
                for(j in 0 until w) {
                    square[i][j] = 'R'
                }
            }
        }
        // 行を塗った後のマス目（都度コピーするのでコピー元として定義）
        val rowFilledTemplate = square.map { it.clone() }

        // 列の選択状態を表すビット列の列挙
        for(wBit in 0 until (1 shl w)) {
            // ビット列を走査して各桁のビットが立っているか判定
            for(j in 0 until w) {
                if(wBit and (1 shl j) != 0) {
                    // ビットが立っていたらその列を赤く塗る
                    for(l in 0 until h) {
                        square[l][j] = 'R'
                    }
                }
            }

            // 塗り終わったので判定
            if(square.joinToString("") { it.joinToString("") }.count { it == '#' } == k) {
                ans++
            }
            // 次の判定のために元に戻す
            // 初期状態ではなく、行は塗られた状態に戻す
            square = rowFilledTemplate.map { it.clone() }
        }
    }
    println(ans)
}

感想

ネストしたループを書いていてどれが何なのか自分でもよくわからなくなって混乱しました…
コメントは提出後の追記ではなく、混乱回避のために実装時に都度記述するのはありかもしれません。
早く実装したいというのと、コメントをがっつり書いたコードがWAになったらなんか恥ずかしいなどの理由でコメントは避けがちなんですが、それで混乱して却って遅くなったら本末転倒ですしねぇ。

考察

実装

感想

Discussion