🌟

ABC200 C - Ringo's Favorite Numbers 2のメモ

2023/02/11に公開

AtCoder

競プロ

tech

とあるバチャで解こうとしたけど解けなかった問題です。

考えたこと

正直、さっぱりわからなかったのですが…

全探索は間に合わないですが、どうすれば線形時間くらいに抑えられるのかわからない。
数列が来た場合はソートすると嬉しい場合があるので、この問題だとどうなのかは一応考えてみました。この問題はソートによって答えが狂ってしまうことはなさそうだと思ったものの、ソートによる恩恵もよくわからず。

引き算する前に既に200の倍数である数もあるけど、引き算によって変わってしまうのでそのように考えても意味がなく…？（今思えばこれはほんの少し惜しかったかも）

それ以上の考察はできず、即刻解説を見ました。

解説を見て

まず、200で割った余りが同じになる2つの数同士の引き算の結果は200の倍数になるということが書かれていました。言われてみればたしかに、なんですがそのように考えることで何が嬉しいのか？
$A$ の各要素を割った余りがいくつになるかで分類することを考えます。すると、いいことがいくつかあります。
まず、その中ならどの組み合わせでも必ず条件を満たす組み合わせになります。200で割った余りが同じ数で分類しているわけなので。必ず条件を満たすということは全組み合わせを試す必要がなく、単純にその中から2つを選ぶパターン数（あり得る全てのパターン）を計算するだけで、その分類の中での答えを求めることができます。この計算は解説の通り、分類内の個数を $X$ とすると $X \times (X - 1) \div 2$ で求められます。探索する必要がなく、計算によって定数時間で求められるので速いということですね。

もう一つ重要なこととして、200で割った余りが同じになる2つの数同士の引き算の結果は200の倍数になるだけでなく、逆に200で割った余りが異なる2つの数同士の引き算が200の倍数になることはないという性質があります。
そのため、各分類ごとに完全に独立して答えを求められます。他のところに分類された数値との組み合わせは一切考える必要がありません。
ということで、上記計算によって分類ごとに答えを求めた後、それを全て足せば全体の答えになります。

200で割った余りとしてあり得る数は0～199までの200通りしかないので、これは単純に全部計算して足しても十分高速です。

はえ～頭いいっすね。

入力例1で確認してみます。
入力は123 223 123 523 200 2000で、これを200で割った余りで分類すると

[123, 123, 523]
[223]
[200, 2000]
の3つになります。

それぞれについて個数を $X$ として $X \times (X - 1) \div 2$ の計算を行うと、答えは上から3、0、1です。これらを足した4が全体の答えで、これは出力例1と一致します。

実装

$A$ の各要素を割った余りがいくつになるかで分類すると書きましたが、実際にはそれぞれ何個ずつあるかという情報だけあれば十分です。なので、各個数だけを記録します。
最初はMapを使って記録したのですが、配列を使ったほうがシンプルでした。

個数を記録したら、あとはそれぞれについての答えを計算して足し合わせるだけです。
答え、および計算の途中経過は32bit整数の範囲を超える場合があることに注意です。（何敗かしました）

fun main() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toInt() }

    val modCount = LongArray(200)

    for(a in aList) {
        val mod = a % 200
        modCount[mod]++
    }

    var ans = 0L
    for(i in 0..199) {
        val x = modCount[i]
        ans += (x * (x - 1)) / 2
    }
    println(ans)
}

感想

これが灰diffなんですか。やべえ。
こういうのを自力で発想できるようになる気がしないんですが、どうしたらいいんですかね… 浴びるように問題を解きまくるしかないのかね。

（執筆時間：39分11秒）

考えたこと

解説を見て

実装

感想

Discussion