🗂

AtCoder Beginner Contest 356参加記

2024/06/02に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 356に参加したので記録を残します。
https://atcoder.jp/contests/abc356

今回は3完で、そこまで遅くなかったのでまあまあという感じ。

A - Subsegment Reverse

数列を作ってから3つに分割して、2番目だけ反転します。Aにしては面倒。
0-indexedのままやったのと、subListが半開区間で指定するので混乱。添字ガチャしているので良くない…

fun main() {
    val (n, l, r) = readln().split(" ").map { it.toInt() }

    val list = (1..n).toList()

    val a = list.subList(0, l-1)
    val b = list.subList(l-1, r)
    val c = list.subList(r, n)

    println((a + b.reversed() + c).joinToString(" "))
}

B - Nutrients

やることとしては栄養素ごとの合計値を求めて、全てが基準値以上かどうか調べるだけなんですが、文字が多くてなんか混乱。
ここまでで10分もかかっていて、これは良くない。

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }
    val x = List(n) {
        readln().split(" ").map { it.toLong() }
    }

    val array = LongArray(m)

    for(i in 0 until n) {
        for(j in 0 until m) {
            array[j] += x[i][j]
        }
    }

    if(a.zip(array.toList()).filter { it.first <= it.second }.size == m) {
        println("Yes")
    } else {
        println("No")
    }
}

C - Keys

これも文字が多くて辛い。組み合わせが $2^N$ 通りあるとわざわざ書いてくれているのは親切ですね。bit全探索で解けると教えてくれているようなものです。 $2^{15}$ 通りなら全部見ても全く問題なし。

bit全探索で列挙するのは鍵の真偽の組み合わせですね。全てダミーという組み合わせから全て正しいという組み合わせまでを全部列挙します。組み合わせを1つ選んだら、各テストケースと矛盾しないか見ていって、全てに対して矛盾がなければ答えをインクリメントです。

テストケースと矛盾がないかどうかの調べ方は若干悩みましたが、本物の鍵だけを含む集合を作って、テストケースのほうも使う鍵の集合を持っておいて、それらの積集合の要素数が $K$ 以上かどうかを見ればいいとわかりました。その場合の要素数が $K$ 以上なのに'x'だったら矛盾していますし、 $K$ より小さいのに'o'でも矛盾していると言えます。

import java.util.Scanner

fun main() {
    val (n, m, k) = readln().split(" ").map { it.toInt() }

    val scanner = Scanner(System.`in`)

    val cases = mutableListOf<Case>()

    for(i in 0 until m) {
        val c = scanner.nextInt()
        val list = mutableListOf<Int>()
        for(j in 0 until c) {
            list.add(scanner.nextInt())
        }
        val r = scanner.next()

        val case = Case(c, list.toSet(), r == "o")
        cases.add(case)
    }

    var ans = 0

    bitmask(n) { bits ->
        val trueSet = bits.mapIndexed { index, b -> index to b }
            .filter { it.second }
            .map { it.first + 1 }
            .toSet()

        var flag = true
        for(case in cases) {
            val set = trueSet intersect case.keys
            if(!(set.size >= k && case.r || set.size < k && !case.r)) {
                flag = false
                break
            }
        }
        if(flag) {
            ans++
        }
    }
    println(ans)
}

data class Case(
    val c: Int,
    val keys: Set<Int>,
    val r: Boolean,
)

fun bitmask(n: Int, action: (List<Boolean>) -> Unit) {
    val limit = 1 shl n
    for(i in 0 until limit) {
        val bits = i.toString(2).padStart(n, '0')
        action(bits.map { it == '1' })
    }
}

bit全探索はライブラリ化しておいたので少し楽できました。しかし定数倍を全く考えていないので遅いんですよねぇ。そのうち高速化しようかな。

あと、テストケースの入力が地味に面倒でした。型が混在しているし、可変だし。いつも使っているreadln()のような一行をまとめて読み込む関数だと面倒だったのでScannerを使いました。

D - Masked Popcount

これは解けませんでした。手も足も出なかったというほどではなく、それなりに考察は進みました。

まず、 $N$ がバカでかいので一つ一つ数えるのは当然無理。とりあえず $M$ を二進数で考えた時、求めるのはANDなのでビットが0の桁については $k$ がどんな数であっても0個になります。逆にビットが1だったら個数にカウントする可能性があります。その場合は $k$ 次第になりますが、 $k$ は1ずつ増えていく、つまり規則性があるので、どういう規則で値が変動していくのか観察するのがよさそう。

たとえば $N$ が15であれば、 $k$ は以下のように変動します。

0から始めるので16個の数値になりますが、桁ごとに見ると、どの桁についても1は8個ずつあることがわかります。16の半分で8個になっているっぽい。（他の数で試しましたが同様でした）

なので $N$ が2の乗数から1引いた数なのであれば、 $M$ の対応する桁が1の場合は $N \div 1$ を足していくことだけで求められそうだとわかりました。
ただ、 $N$ がそれ以外の数ならそうもいきません。とりあえず、 $N$ 以下の数値の中で最大の「2の乗数から1引いた数」までは簡単に求められるので、余った数をそれとは別に計算という感じでできないかと考えました。各桁ごとに、1が出現する頻度には明らかに規則性があるので正しく計算すれば求められるのですが、計算力が足りなくて結局解ききれませんでした。悔しい…

コンテスト後、ChatGPTに相談してみました。微妙に誤った答えを返してきたのですが、噛み砕いてみるとやはり各桁ごとに1が出現する規則性を使って求めるようでした。結局、ChatGPTが生成したコードを修正して通ったのが以下です。

import java.math.BigInteger

fun main() {
    val (n, m) = readln().split(" ").map { it.toLong() }

    val mod = BigInteger("998244353")

    println(countOnesInBinary(n.toBigInteger(), m) % mod)
}

fun countOnesInBinary(n: BigInteger, m: Long): BigInteger {
    var bitPosition = BigInteger.ONE

    val bits = m.toString(2).toList().reversed()

    val counts = mutableListOf<BigInteger>()

    while (bitPosition <= n) {
        var count = BigInteger.ZERO

        val fullCycles = (n + BigInteger.ONE) / (bitPosition * BigInteger("2"))
        val remainder = (n + BigInteger.ONE) % (bitPosition * BigInteger("2"))

        count += fullCycles * bitPosition
        if (remainder > bitPosition) {
            count += remainder - bitPosition
        }

        bitPosition *= BigInteger("2")
        counts.add(count)
    }

    return bits.zip(counts).filter { it.first == '1' }.map { it.second }.sumOf { it }
}

2進数なので1の位、2の位、4の位... と増やしていって考えるのですね。その桁ごとの合計値を求めます。あとは $M$ の桁が1だった場合はそれを足していくのですが、この計算は右側からやっているので $M$ の2進数文字列は反転してから照合しています。

感想

まあCで事故らなかったのと、Dも解けなかったけどそれなりに考察が進んで楽しかったですね。コンテスト直前はなんかテンションが低かったのですが、それでも参加してよかったですね。直近だと精進できていないのですが、コンテストにまで出なくなったらおしまいなので、多少テンションが低くともできるだけ参加していきたいですねｗ
（執筆時間: 47分35秒）

A - Subsegment Reverse

B - Nutrients

C - Keys

D - Masked Popcount

感想

Discussion