AtCoder Grand Contest 009 E - Eternal Average

解説をみてピンと来なかったところを補足する形の自分用のメモです。

f:id:baitop:20211210233005p:plain

まず、K個を足して平均に置き換えるという操作は分かりにくいので

上のように操作をK分木で表す事にする

そして、1の頂点の深さをa1....am

0の頂点の深さをb1.....bnとする

すると最終的な値をxとした時に

それぞれの要素についての最終的な寄与を考えると

x = k^(-a1) + ... k^(-am)である事が分かる

また、ここで実はすべての葉が1の場合はxが必ず1になる事が分かる。

なぜならその場合、下のようにk個を取った平均が常に1になりつづけるからである

f:id:baitop:20211210233611p:plain

よって以下の等式が得られ

1 = k^(-a1) + ... k^(-am) + k^(-b1) + ... k^(-bn)

x = k^(-a1) + ... k^(-am)

1-x = k^(-b1) + ... k^(-bn)

である事が分かる、以後はここから更に必要な条件について考えていく。

xをK進数(つまり各項は0~K-1)で

x = 0. x1 x2 x3...xtと表す事にし(ここでxt!=0)

1-x = 0.y1 y2 y3..ytとすると

x1+...+xt <= mである事が分かる

また、一回繰り上がると全体の合計がK-1だけ減る事から

(x1+...+xt) % (K-1) = m % (K-1)となる

ここで1-xの式について同様に考えると

y1+...+yt <= n

(y1+...+yt) % (K-1) = n % (K-1)が得られる

よってこれらの条件を満たす必要がある事が分かるが、条件を満たす任意の木を構築できる。

これを示すには、x1...xt, y1....ytについてz1...ztをzi = xi + yiとした時に

任意のiについて、深さがiであるような葉がzi個存在する木を構築できれば良いが

z1~z(t-1) == K-1 かつ zt == Kである事を考えると下のように木を作れて

それぞれの葉に0と1を割り振る事が出来る

f:id:baitop:20211210234913p:plain

ただ現状では0の個数がM, 1の個数がNに満たない場合がある

その際は例えば0をK-1個増やしたい場合は、0の葉にK個の0を子に持たせてやれば

よい。

よって上が必要十分条件だと分かる。

dp[t][s] := t桁見た時に全体の桁和がsになるような場合の数として

あとはt(桁数)の値について今までの桁和(s)を持ち、t桁目で使う1の個数をnsとした時に

桁数が小さい事から以下の様なループで計算量はO((M+N)^2)で回せる

rep(t, 1, max_keta) {
    rep(s, M + 1) {
        //i+1で終わらせる場合
        //nsは1以上
        rep(ns, 1, K) {

後は1の個数がM以下かつ K-1で割った余りがMと合同であるかなどを0についてもやりdpを更新していけばよい

バイトの競プロメモ