🌟

ABC 178 C - Ubiquityのメモ

2022/10/13に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。（解けたとは言っていない）

考察

※だいぶ明後日の方向に行っているのですが、せっかくなので残しておきます

とりあえず小さいケースで考えてみます。

数列は0と9の両方を含む必要がありますので、Nが1の場合は0です。
Nが2の場合、明らかに[0, 9]と[9, 0]の2通りしかありません。
Nが3になるとどうなるか。とりあえず列挙してみたところ、以下の54通りでした。

増分で考えるとけっこう変則的で、法則を見出すのが難しいです。

よくわからないのでNが4の場合を考えてみます。全体としては974通りだったのですが、合計だけ見てもよくわからないですね。
こういう場合はどれかを固定して考えてみると何かわかる場合があります。とりあえず1つ目を1で固定して考えてみます。
その場合は54通りあることがわかりました。54とは前に見た数字ですね。考えてみたら当たり前でした。1つ目を固定したら残り3つなので、Nが3の場合と同じことになります。
1つ目が0の場合と9の場合は別にすると、1の場合から8の場合までは全て同じそれぞれ54通りずつのはずです。法則っぽいものが見えてきました。

つまり、あるNの場合の答えは(N - 1)の場合の答えを利用して求めることができるわけですね。Nを1ずつ増やしながら数えていくと。
ということは、これはアレですね？DPですね？？DPなんですね？？？

じゃあこれで解けるかというと、まだです。見なかったことにしていた、1つ目が0の場合と9の場合を考える必要があります。
1つ目を0で固定した場合は、もう0のことは考えなくてよくていずれかの桁に9を含む場合を数えればいいです。9で固定した場合も考え方は同じです。

ただ、この辺りでMPが切れました…ｗ
頑張れば解ける可能性も感じましたが、何時間かかるかわからないのでこのへんでギブアップしておきます。

解説を見て

解説ではDPを使ってなかったのでずっこけました…
動画ではDPでもできるとは言っていたのでたぶん間違ってはいないと思うんですが、もっとずっと簡単な方法があったのですね。
（DP解法の場合、三次元と想像以上の難易度になるようなので見なかったことにしました）

包除原理という言葉は初めて知りました。理解したとは言い難いですが、とにかくベン図の足し引きで答えを求められるんですね。ベン図自体は知っていますが、そういう計算ができるものだとは思っていなかったです。
まあこの問題を見てベン図を発想しなかったので、使いこなせているとは全く言えないですね。包除原理以前にベン図のことを意識したほうがいいですね…

今回のケースだと0を含む集合と9を含む集合との積集合ですが、包除原理では和集合を求めることもできるっぽいです。（チラ見しただけでちゃんと読めてないですが）

今日はもう色々限界なのでほぼ書き写しです…

private const val mod = 1000000007

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

fun main() {
    val n = readLine()!!.toInt()
    var ans = powMod(10, n) - powMod(9, n) - powMod(9, n) + powMod(8, n)
    ans %= mod
    ans = (ans + mod) % mod
    println(ans)
}

教訓

集合について考える場合はベン図を使う
積集合、あるいは和集合を求めるのに包除原理というものを使える場合がある
- よくわかってないけど単語と雰囲気は覚えておく
- 次にそれっぽい問題に当たったら遅延評価勉強法で理解に努める…

考察

解説を見て

教訓

Discussion