AtCoder Beginner Contest 280 A～Dのメモ

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)に参加したので記録を残しておきます。
https://atcoder.jp/contests/abc280

A - Pawn on a Grid

全体の'#'の個数を数えるだけです。文字列を全部結合してから数えるほうが簡単だったかも。

fun main() {
    val (h, w) = readLine()!!.split(" ").map { it.toInt() }
    val s = List(h) {
        readLine()!!
    }
    println(s.map { it.filter { it == '#' }.length }.sum())
}

B - Inverse Prefix Sum

$A_k$は、$A_1$から$A_{k-1}$までの合計値を$S_k$から引けば求められます。また、$A_1$は必ず$S_1$と等しいです。ちょっと考え込んでしまいましたが、等式を変換すれば一発でしたね…
数学できません。

fun main() {
    val n = readLine()!!.toInt()
    val s = listOf(0) + readLine()!!.split(" ").map { it.toInt() }

    val ans = mutableListOf<Int>()
    ans.add(s[1])
    var sum = s[1]
    for(k in 2..n) {
        val v = s[k] - sum
        ans.add(v)
        sum += v
    }
    println(ans.joinToString(" "))
}

C - Extra Character

文字を先頭から一文字ずつ比較していって、最初に不一致だった位置が答えです。計算量は$O(N)$ですが、それでも普通に間に合う程度の制約です。
ただ、末尾に足された場合を考慮する必要があります。

fun main() {
    val s = readLine()!!
    val t = readLine()!!

    for(i in s.indices) {
        if(s[i] != t[i]) {
            println(i + 1)
            return
        }
    }
    println(t.length)
}

末尾に足された場合については見逃さなかったのに、その場合は末尾の文字を出力する（！？）とかいう意味不明なコードを書いてWAをもらいました。自己嫌悪に陥るレベルの大失態です。

見ての通りC問題とは思えないくらい簡単なので、これが致命傷となって見事に灰パフォとなりました（）

D - Factorial and Multiple

失態を取り返そうと頑張ってみましたが、無理でした。

コンテスト中の考察

とりあえずサンプル2から、素数がポイントというのは感じました。123456789011はどうやら素数で、素数ということは他の数を使った乗算によって作ることはできないため、K自身が答えになると。
よくわからないけどとりあえず素因数分解してみようとか、その最大値だとサンプルが通るのでとりあえず提出してみようとかってやってましたが、それ以上はわかりませんでした。
それでサンプルが通ったのは完全にただの偶然ですね。最小とは限らないけど一応倍数にはなるのかなと根拠もなく思っていましたが、全然そんなことはなく…

解説を見て

まず、答えとなるN以降はNがどのような値になってもKの倍数になるということでした。まあ階乗なので言われてみればそうですね。それで、その性質を利用して二分探索ができますよと。
（ある数がNGならそれより前は探索しなくていいし、ある数がOKならそれより後は探索しなくていい）
それで$1!$がKの倍数であることはなく、$K!$は確実にKの倍数なのでその範囲で探索すればいいと。
なので、探索対象の値それぞれの階乗がKの倍数かどうかを現実的な計算量で判定することができれば答えが求められるということでした。

実際に階乗を計算してKで割り切れるかというのはもちろん計算量的に無理なので、他の方法を考える必要があります。結論としては、素因数分解とルジャンドルの定理を組み合わせるとできるということでした。
ルジャンドルの定理というのは全く知りませんでしたが、これを使うとある素数$p$で$N!$を何回割ることができるか求められます。$N!$の実際に計算した値ではなく、$N$からそれを求められるということですね。$N!$を素因数分解した時の、素数$p$の指数を求められるともいえます。
それで$N!$がKの倍数であるためには、Kを素因数分解して得られた素数全てが$N!$に含まれる必要があります。すみません、数学できないので「含まれる」は数学的に正しい言い方じゃないとは思いますが、要するに割り切れるということを言いたいです。それはルジャンドルの定理で判定できます。Kを素因数分解して得られた素数の一つ一つについてルジャンドルの定理を適用して割れる回数を求めます。素数の指数と求めた回数を比較して、前者のほうが大きい場合は、なんというか、割られる分の素数が足りませんので、$N!$はKの倍数ではないといえます。逆に、全ての素数について、なんというか、足りているのであれば$N!$はKの倍数です。
（雑な表現ですみません。数弱がわかったような気になるための方便です）

ルジャンドルの定理によってわかるのはあくまでも$N!$がKの倍数かどうかなので、最終的な答えとなる最小値かどうかまではわかりません。それを求めるのは二分探索でということですね。

素因数分解、ルジャンドルの定理、二分探索をパーツとして作ってしまえば、あとは簡単に組み合わせるだけなんですね。シンプルでびっくりしました。
素因数分解、ルジャンドルの定理、二分探索の実装は各所から書き写したようなもので、所与のものとして使えてしまうので内容の理解には及んでいません。
（ライブラリ化しちゃおうと思います）

二分探索については、ライブラリ化しやすいように判定個所を関数として受け取るようにしています。

import kotlin.math.abs

fun main() {
    val k = readLine()!!.toLong()

    val pes = primeFactorial(k)

    val isOk: (Long) -> Boolean = { n ->
        var result = true
        for((p, e) in pes) {
            if(legendre(n, p) < e) {
                result = false
                break
            }
        }
        result
    }

    println(binarySearch(1, k, isOk))
}

// ルジャンドルの定理
fun legendre(n: Long, p: Long): Long {
    var res = 0L
    var p2 = p

    while (true) {
        val tmp = n / p2
        if(tmp == 0L) {
            break
        }
        res += tmp
        p2 *= p
    }
    return res
}

// 素因数分解
fun primeFactorial(paramN: Long): List<Pair<Long, Long>> {
    val result = mutableListOf<Pair<Long, Long>>()
    var n = paramN
    var a = 2L
    while(a * a <= n) {
        if(n % a != 0L) {
            a++
            continue
        }
        var ex = 0L

        while (n % a == 0L) {
            ex++
            n /= a
        }
        result.add(a to ex)
        a++
    }
    if(n != 1L) {
        result.add(n to 1)
    }
    return result
}

// 二分探索
fun binarySearch(minNg: Long, maxOk: Long, isOk: (Long) -> Boolean): Long {
    var ng = minNg
    var ok = maxOk

    while(abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if(isOk(mid)) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

感想

今回は全くいいとこなしでしたね。なかなかメンタルにきましたが、D問題の解説を一応自分なりに消化して記事にしたことでだいぶ回復しました。

Cが簡単すぎるのはいかがなものかというお気持ちも少しありますが、Cまでを速く正確に解けなかったのと、Dが解けなかったのは力不足でしかないので、これからも力をつけていきたいと思います。