Chef and Digits
Problem Code: DGTCNT
各数字が出現した回数を覚えるような桁DPで攻めると駄目。
数字の集合S subset {0,...,9}を決めたとき、F(S, N):=#{Sに含まれる数字の出現回数が条件に一致するような0超過N以下の数}を求める。このときSに含まれないものはどうなってもいいとして、包除原理で辻褄があう。
F(S, N)は組合せを駆使して求める。
L以上R以下の条件があるので、solve(N) = \sum_S mu(S) F(S, N)とした時にsolve(R) - solve(L-1)が解。ただしmu(S):=(-1)^|S|。
(CH) Serejs and Billiards
Problem Code: SEABIL
タイブレーク。ビリヤード。衝突すると値を吸収するのでどちらかと言えば雪だるま？
対角線に集める→最後の一突きでポケットに落とす、この方針でよい。
各行に対して、一突きで全てまとめて対角線に移動させる。これでN+1回で全ての玉を落とせる。
負のボールは巻き込まないようにずらすとスコアがよくなる。
Editorialが空。トップスコアの九分九厘九毛取らなければ上位になれない、辛い。
Heavy-Light Decomposition
Problem Code: HLD
知識として、HLDのクエリ計算量がO(log^2 n)なので解の上限はO(log^2 n)である。
dp[v][i] := x; 頂点vの上に長さxのheavy edgeを付けてもスコアはi以下
これを木DP。
iの上限を100で見積もるとWA、200だとTLEした。200で多少の枝刈りしてAC。
つまり、N=1e5のHLDのクエリは100を超えるノードを読む必要があるということ、最小のHLDでなかったり、segment treeを置いたりすると200を超えることもありそう。
