HHKB Programming Contest 2022(AtCoder Beginner Contest 235)
中盤、妙に制約が厳しめの問題が多かった。
制約や問題文が見るからに桁DP。あと使った数字の集合も持ちたいのでbitDPも絡んでくる。
桁が log10N≤104 個、1桁あたりの遷移に M×2M≲ かかるので、
ちょっときつくないか?という感じはするものの、他に方法も思いつかない。
まぁ遷移はシンプルなので下手な書き方さえしなければいけると信じよう。
桁DPは個数を数えさせるものをよく見るが、今回は総和であることに注意。
以下のDPを定義する。
公式解説では、使った数字の集合を C_i に関係なく 0~9 の全てで区別しているが、
ここでは C_i に含まれる数字のみで区別している。
S をbit集合で表現すると、答えは DP_{total}[N][2^M-1] となる。
ただし N 自身も条件を満たす場合、それは含まれていないので最後に足す。
桁DPは、区別すべき状態が S の他にも暗黙的に存在するため、きちんと分けて遷移を考える必要がある。
②は、問題によっては①と同等に扱ってよいこともあるが、今回は C_i=0 があった場合に 先頭に出てくるか途中に出てくるかで意味合いが異なるため、分けて考える必要がある。
②③に該当する状態も、ある桁で①に変化すればそこからDPに含めてやる必要がある。
その際、特に③で必要になるため、以下の情報も合わせて管理する。
1桁目に関しては、下記の遷移のどれとも異なるため、個別に行う。1桁目の数字を d とすると、
0を置いた場合②、d を置いた場合③の状態になり、1~d-1 を置いた場合に①としてDPの管理対象になる。
更新できる数字の範囲が違うだけで、式は②と同様となる。
i+1 桁目に 0~9 の何を置いてもよい(N 以下という条件が破られることはない)。
数字 d を置くとして、以下のような遷移となる。遷移先のみが異なる。
N=30000, C=(1,3,5) として、DP_{total}[3][0b011] には 103, 113, 31 などが該当し、その総和が記録されている。
4 桁目に 5 を付け足す場合、1035, 1135, 315 などの総和を DP_{total}[4][0b111] に加えたい。
それには、DP_{total}[3][0b011] を10倍した上で、個数分だけ 5 を加えればよいので、上のような遷移となる。
この状態に該当するパターン数は常に1通り、総和は0。
i+1 桁目にも0を置いた場合はこの状態が継続される。
2桁目以降、1~9 を置いた場合はDPの管理対象となる。
①と同じような遷移となるが、パターン数と総和が決まっているためシンプルになる。
この状態に該当するパターン数も常に1通り、総和は just_{total}。
N の i+1 桁目を g とすると、g を置いたらこの状態が継続される。
g を超える数は N を超えるので論外。
0~g-1 の数を置くと、N 未満になることが確定し、DPに含められる。d を置くとして、
仮に、何も植わっていない庭を許すとするならば、各作物独立に考えてよくなるので簡単になる。
とすると、f(N,A) \times f(N,B) \times f(N,C) で求められる。
こういう場合は包除原理が使えそう。つまり、
少なくとも0個の庭に何も植わっていない場合数 - 少なくとも1個の庭に何も植わっていない場合数 + 少なくとも2個の庭に何も植わっていない場合数 ... +/- 少なくともN個の庭に何も植わっていない場合数 ----------------------------------------------- = 答え
少なくとも k 個の庭に何も植わっていない場合数は、以下をかけあわせた数となる。
ただし n \lt r の場合、{}_nC_r=0 とする。
上記の数え方だと、例えば以下の2つは結果的に同じなのに別々に数えられている。
一般に、数え上げでは重複に気をつけることが多いので、 それっていいの?と躊躇してしまうが、包除原理の場合は 「確実に植わっていない特定の k 個」が異なっていれば後から適切に除かれるのでこれでいい。
「植えないと決める対象とする/しない」を各庭に対して決めた 2^N 通りについて、 対象数が偶数なら正、奇数なら負で場合数を足し合わせるという手法が本来の包除原理であり、 今回は対象数が同じもの同士をまとめられるのでまとめている、と考えられる。
さて、これで k=0~N について f(N-k,A) \times f(N-k,B) \times f(N-k,C) を求めればよいとわかった。
しかし f の内部では二項係数を 0~A まで足し合わせているため、k をあわせるとまだ O(N^2) かかる。
f(n,A) と f(n+1,A) の差分に着目する。
f(N,A) が表しているのは、パスカルの三角形の N 段目の、左から第 A 項までの和である。(0-index)
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 f(5, 3) = 1+5+10+10 = 26 f(4, 3) = 1+4+6+4 = 15 f(3, 3) = 1+3+3+1 = 8 f(2, 3) = 1+2+1 = 4 f(1, 3) = 1+1 = 2 f(0, 3) = 1 = 1
パスカルの三角形は、自身の斜め上の2つの数字の和が、自身の値となる。
そのため、f(n,a) と f(n+1,a) を比較した場合、 n 段目の数字はほとんど n+1 段目には左右に2回ずつ波及している。
唯一、一番右端の第 a 項のみ、左にしか波及しない。
1 4 6 4 ↙↘↙↘↙↘↙ × 1 5 10 10 -
よって、まず f(0,A)=1 からスタートし、 f(n+1,A)=2f(n,A)-{}_nC_{A} として逐次的に計算していくと、 O(N) で f(0,A)~f(N,A) を全て求められる。
二項係数周りで「O(N) を O(1) にする」便利な公式は多数あるけど、 こういう「O(N^2) を O(N) にする」テクニックは検索に頼りづらい。