🙌

競プロ典型 90 問 075 - Magic For Balls（★3）のメモ

2023/11/26に公開

AtCoder

競プロ

tech

なんとなく見てみて解きました。

こういう、考えたことを実装から逆算するのが難しい感じの問題は悩ましいですね…
数学できる人なら普通に逆算できるのかな？

考察

まず、全てのボールを同時に叩くことができることから、可能な限り均等に分けていくのが最適のはずと思いました。しかし、実際にそれをシミュレーションする実装はなかなか大変そうです。 $⌊\sqrtN⌋$ で割れるならそれを使えばいいのですが、割れない場合は探す必要がありますし、しかもそれを再帰的に実行する必要があり…
さらに、割った後に最終的な処理回数に影響するのは「素数になるまで割る回数」が多いほうなのですが、これは単純な数値の大小だけではわからず、素因数分解しないとわかりません。ということでとてもやってられません。
じゃあどうするのか考えてみると、まあ個別に素因数分解するのは馬鹿らしいので $N$ 自体を素因数分解しておいてそれをもとに考えるのがよさそう。
結論としては、素因数分解して素因数の個数を求めて、それが2で割れる回数が答えとなります。割った後に最終的な処理回数に影響するのは「素数になるまで割る回数」が多いほうだと書きましたが、これは全てのボールを同時に叩けるため、割る回数が多いほうを処理しているのと同時に少ないほうも処理できますので、多いほうの処理が終わった頃には少ないほうも絶対処理が終わっているからです。
なので、 $a,b$ に分けた時には割る回数が少ないほうは無視して、多いほうをさらに $a,b$ に分けて、またそのうち多いほうを分けて… を繰り返せば答えがわかります。あとは $a,b$ をどのように分ければいいのかですが、可能な限り均等にしたほうがいいというのはわかっているので、ここで素因数の個数に着目します。均等に分けるので、個数を半分ずつにしていくのが最適となります。というわけで、最終的には素因数の個数を2で割れる回数が答えということになります。
個数が最後までずっと2で割り続けられるとは限りません。途中で奇数になるかもしれませんが、たとえば5なら2と3に分けるというように考えれば問題ないです。これは実際の計算としては切り捨てで割って、そのうち片方に1を足すとすればいいです。

実装

fun main() {
    val n = readln().toLong()

    val pf = primeFactorial(n)
    val count = pf.sumOf { it.second }

    var num = count
    var ans = 0

    // 2で割れる回数
    while (num != 1L) {
        num = if(num % 2 == 0L) {
            num / 2
        } else {
            num / 2 + 1
        }
        ans++
    }

    println(ans)
}

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
}

（執筆時間: 28分18秒）

考察

実装

Discussion