🐈

ABC050 C - Lining Upのメモ

2023/05/21に公開

AtCoder

競プロ

tech

解いてみました。

今回のはほんとにしょうもないメモです。解けたというか、なんかそれっぽいことしたら通っちゃいました。
なので理解していないですが、なんかそれっぽいこととは何なのかを一応覚えているうちに書いておきます。

それっぽいこと

1から $N$ までの数で、申告した人数を数えました。すると、申告した数は（正しいのであれば）必ず0か2になることがわかりました。しかも、0と2が交互になります。
たとえば例1だと、入力は以下の通りです。

5
2 4 4 0 2

これらについて1から $N$ までの数の申告数を数えて並べると以下のようになります。

0 2 0 2 0

1, 3, 5を申告した者はおらず、2と4を申告した者が2人ずつです。

例3だと同様に入力が

8
7 5 1 1 7 3 5 3

これで、同様に申告数を数えて並べると

2 0 2 0 2 0 2 0

となります。0か2のどちらで始まるのかは違いがありますが、前述の通りいずれも0か2しかなくて交互に出現します。
0か2のどちらで始まるかは、 $N$ が偶数か奇数かで決まると思われます。

そして例2について見ると

7
6 4 0 2 4 0 2

0 2 0 2 0 1 0

となります。1が出現しています。例2は申告が間違っている例なので、0か2以外が出現したら申告に矛盾があると判断できそうです。
あとは偶数か奇数かで決まる周期が異なる場合も矛盾といえそう。

そして、例1と3の答えはいずれも2の乗数であることと、次数が上記の2の出現回数と一致していることに気づきました。

なぜなのかは全然わかっていないですが、申告に矛盾がないことを確認してから、矛盾がない場合は2の出現回数をもとに乗数を求めれば答えになるっぽいという仮説を立てました。

結局、以下の実装になりました。（そして通った…）

import kotlin.math.abs

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

    val map = mutableMapOf<Int, Int>()
    for(a in aList) {
        map[a] = map.getOrDefault(a, 0) + 1
    }

    var count = if(n % 2 == 0) {
        2
    } else {
        0
    }

    for(i in 1..n) {
        if(map.getOrDefault(i, 0) != count) {
            println(0)
            return
        }

        count = abs(count - 2)
    }

    println(powMod(2, map.filter { it.value == 2 }.count()) % mod)
}

const val mod = 1000000007

fun powMod(x: Long, y: Int): Long {
    var res = 1L
    repeat(y) {
        res = res * x % mod
    }
    return res
}

答えは $10^9 + 7$ で割った余りなので、随時modをとる必要があります。
ここで、以前別の問題で使ったpowModを持ってきました。

Pythonには標準であるみたいですが、Kotlinには（たぶん）ないので自作です。以前解説を見ながらほぼ書き写したものですが。

なぜこれで通るのかの理解についてはまたいずれ…

（執筆時間: 28分27秒）

それっぽいこと

Discussion