🌊

ABC190 C - Bowls and Dishesのメモ

2023/01/01に公開

AtCoder

競プロ

bit全探索

tech

目についたC問題を解いてみるの回です。

考察

入力値にグラフっぽさがありますが、実際にはグラフの走査のようなことはせずにbit全探索で解けます。

$K$ 人の人が $C_i$ か $D_i$ のどちらか一方にだけボールを置きますので、ビットが0だったら $C_i$ に置く、1だったら $D_i$ に置くというように考えることが可能です。

全員が $C_i$ に置く場合から全員が $D_i$ に置くパターンまで全部試せばよく、そのためにbit全探索が使えます。
全パターンだと $2^{16}$ 通りですが、 $K$ が最大でも16なので計算量の問題はありません。
（ $2^{16}$ はたかだか65536）

全員がボールを置いた状態を記録したら、 $M$ 通りを全て実際に確認して何通りが条件を満たすかを数えます。
$2^{16}$ と $M$ のかけ合わせになりますが、 $M$ の最大値も100と小さいので問題ありません。

実装

import kotlin.math.max

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val ab = List(m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        a to b
    }

    val k = readLine()!!.toInt()
    val cd = List(k) {
        val (c, d) = readLine()!!.split(" ").map { it.toInt() }
        c to d
    }

    var ans = 0
    for(mask in 0 until (1 shl k)) {
        val bucket = IntArray(n+1)
        for(i in 0 until k) {
            val (c, d) = cd[i]
            if(mask and (1 shl i) == 0) {
                bucket[c]++
            } else {
                bucket[d]++
            }
        }

        var cnt = 0
        for(i in 0 until m) {
            val (a, b) = ab[i]
            if(bucket[a] != 0 && bucket[b] != 0) {
                cnt++
            }
        }

        ans = max(ans, cnt)
    }
    println(ans)
}

上に書いた通り、ビットが0だったら $C_i$ に置く、1だったら $D_i$ に置くと考えています。全員が $C_i$ に置く（ビットが全て0）の場合も確認する必要があるので、maskは0から始めないといけません。

ボールが置かれた皿の状態をbucketという配列で管理しています。 $A, B, C, D$ が1-indexedなのでそれに合わせられるようにn+1を確保しています。初期値はデフォルトで0です。何も置かれていない状態は0で表せるのでそのままでOKです。
ボールが置かれた状態は各パターンで独立なのでbucketはループ内で宣言しています。

$C_i$ と $D_i$ のうちボールを置くほうをインクリメントします。よく見たらそれぞれの人が何個ボールを置くのかは問題に明記されていませんが、個数が0かそうでないかだけが重要なので何個と考えても問題なさそうです。

全てのボールが置かれた後の状態を記録したら、 $M$ 個の条件それぞれをチェックすればいいです。

考察

実装

Discussion