🌊

ABC190 C - Bowls and Dishesのメモ

2023/01/01に公開約1,700字

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

https://atcoder.jp/contests/abc190/tasks/abc190_c

考察

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

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

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

Discussion

ログインするとコメントできます