ABC227 C - ABC conjectureのメモ

目についたC問題を解いてみるの回です。
https://atcoder.jp/contests/abc227/tasks/abc227_c

考察

愚直な実装だともちろん間に合いません。欲しいのは個数だけなので、計算で求めることになります。
思考の出発点として、3つのうち2つが決まったら残りはどうなるのか？を考えてみました。

たとえば(1, 1, C)の場合にCはどうなるか。この場合、Cは1をかけてもN以下になる整数なので、1～Nになることがわかります。個数でいうとN個です。

次に(1, 2, C)だった場合。ちょっとわかりづらいので具体的な数で考えてみます。たとえばNは100であるとします。その場合、Cは2～50ですね。CはB以上なので、1になることはありません。個数でいうと49個です。

次は(1, 3, C)だった場合。同様にNは100であるとすると、Cの範囲は3～33です。個数は31個です。
ここまで来ると、この33といった数を求めるのに無意識に計算していたことに気づきます。つまり、100 ÷ 3です。この商が33というわけです。なので、この時点ではNをBで割った数からB - 1を引いた数が個数となっていそうです。Bより小さい数を除外なので、B - 1です。

ただ、実際にはA * Bで割る必要があると思います。上記はAが1なのでBで割った数となっていそう。なのでAが2以上の場合でも考えてみます。
(2, 3, C)としてみます。Nが100とすると、Cは3～16です。やはりN ÷ (A × B)になっていますね。

これでAとBを探索すればCは探索しなくていいことがわかりました。しかし、まだ十分ではありません。AとBの探索範囲が広いとやはり間に合いません。
AとかBをNまで探索するのは明らかに無駄です。A、B、Cには大小関係があるので、Aは必ずB以下、Bは必ずC以下です。そう考えると、Aの上限はNの3乗根だとわかりました。3乗したらNになる数です。それより大きい場合はBとCをかけると必ずNを超えてしまいます。
3乗根は整数になるとは限りませんが、おそらくその場合は切り捨てでいいでしょう。

ここまでわかれば実装できそうです。実装してみます。

import kotlin.math.max
import kotlin.math.pow

fun main() {
    val n = readLine()!!.toLong()
    var ans = 0L

    val root3 = n.toDouble().pow(1.0 / 3).toLong()

    for(i in 1..root3) {
        for(j in i..root3) {
            ans += n / (i * j) - (j - 1)
        }
    }
    println(ans)
}

i, jじゃなくてa, bにすればよかったですね…
それはさておき、実はこれだとサンプルで答えが合いません。Bの上限も3乗根にしていますが、考えてみたらそれが違いました。BはNの平方根まであり得ます。たとえばNが100だと(1, 10, 10)があり得ます。

import kotlin.math.max
import kotlin.math.pow

fun main() {
    val n = readLine()!!.toLong()
    var ans = 0L

    val root3 = n.toDouble().pow(1.0 / 3).toLong()
    val root2 = n.toDouble().pow(1.0 / 2).toLong()

    for(i in 1..root3) {
        for(j in i..root2) {
            ans += max(0, n / (i * j) - (j - 1))
        }
    }
    println(ans)
}

しかし、これでもダメです。答えは合うのですが、入力例3の場合にちょっと時間がかかっていて、TLEになりそうでした。ただ、全然返ってこないというわけではなく3～4秒で返ってくるのであと一歩な感じです。

まあ、maxとか使っている時点で余分な探索を行なっている自覚があるわけでしてね…
ズルせずにちゃんと考察します。といっても考察というほどのことはしておらず、実際に愚直実装をしてみて実例を見たりしたところ、N ÷ Aの平方根がBの上限とわかりました。まあ考えてみたらそりゃそうですね。

今度こそいけるはずです。

最初の提出

import kotlin.math.max
import kotlin.math.pow

fun main() {
    val n = readLine()!!.toLong()
    var ans = 0L

    val root3 = n.toDouble().pow(1.0 / 3).toLong()

    for(i in 1..root3) {
        val root2 = (n / i).toDouble().pow(1.0 / 2).toLong()
        for(j in i..root2) {
            ans += max(0, n / (i * j) - (j - 1))
        }
    }
    println(ans)
}

しかしダメでした。いくつかのケースでWAが出ます。これは心が折れそうになりますね…

WAの原因を探る

上で愚直実装もやってみたとチラリと書きました。愚直実装ならたぶん合っているので、その結果と上記の提出コードの結果を照合してみればいいんじゃね？と思いました。

こんな感じです。

import kotlin.math.max
import kotlin.math.pow

fun main() {
    for(n in 1..100000000000L) {
        val sol1 = solve(n)
        val sol2 = solve2(n)
        if(sol1 != sol2) {
            println("Error: n = $n, expected=$sol2, actual=$sol1")
        }
    }
}

fun solve2(n: Long): Long {
    var count = 0L
    for(i in 1..n) {
        for(j in i..n) {
            for(k in j..n) {
                if(i * j * k <= n) {
                    //println("($i, $j, $k)")
                    count++
                }
            }
        }
    }
    return count
}

fun solve(n: Long): Long {
    var ans = 0L

    val root3 = n.toDouble().pow(1.0 / 3).toLong()

    for(i in 1..root3) {
        val root2 = (n / i).toDouble().pow(1.0 / 2).toLong()
        for(j in i..root2) {
            ans += max(0, n / (i * j) - (j - 1))
        }
    }
    return ans
}

愚直実装は遅いので、結果が出るまでけっこうかかっちゃうのかなと思ったのですが
全然そんなことはなく、即座に以下の結果が得られました。

Error: n = 64, expected=182, actual=181
Error: n = 125, expected=422, actual=421
Error: n = 216, expected=857, actual=856
Error: n = 343, expected=1522, actual=1521
Error: n = 512, expected=2509, actual=2508
Error: n = 729, expected=3881, actual=3880
Error: n = 1000, expected=5708, actual=5707

まだまだありそうですが、これだけあれば十分なのでそこで止めました。

この場合のNの共通点を考えたところ、すぐに見当がつきました。1000の場合がわかりやすいですが、これは全て3乗根が整数になる数ですね。
3乗根を求めるのに浮動小数点を使っているので、そこで誤差が出て3乗根が整数にならず切り捨ててしまっているのが原因っぽいです。

どうしようか考えましたが、結局以下のようなコードになりました。

再度の提出

import kotlin.math.max
import kotlin.math.pow

fun main() {
    val n = readLine()!!.toLong()
    var ans = 0L

    var root3 = n.toDouble().pow(1.0 / 3).toLong()
    val tmp = root3 + 1
    if(n / tmp / tmp == tmp) {
        root3 = tmp
    }

    for(i in 1..root3) {
        val root2 = (n / i).toDouble().pow(1.0 / 2).toLong()
        for(j in i..root2) {
            ans += max(0, n / (i * j) - (j - 1))
        }
    }
    println(ans)
}

本来切り捨ててはいけない場合に切り捨てられているっぽい時は補正するようにしました。ちょっとアレですが、原因が他にないなら通るはず…

やったぜ

（ところでmaxを消し忘れてますね…なくても動くはずですが。まあそんなに害はないでしょうからいいか）

感想

解けなさそうな難しい問題を選んだつもりだったのですが、時間はかかりつつも解けてしまいました。素直に嬉しいです。
本当は解けずに解説を見て新たな知識を得るつもりだったのですが、まあTLEやWAの対処も含めた一連の流れを経験できたのでそれはそれで有益ですかね。

今までやったことなかったですが、おそらく合っているであろう愚直実装をして結果を比較するというのはバグ取りには有効そうですね。
まあ、愚直実装が容易なシンプルな問題だったのが幸いしました。複雑で愚直実装も時間がかかる問題ならこうはいかなかったかも…