A - CatCoder Binary Contest Editorial
by
Mitsubachi
下の桁から決定する解法です.答えが $X$ 以上となるような条件を考えます.
$X$ 回開催できるかの判定方法としては以下のようなようなものが考えられます.イメージとしては下から決定するというものです.
- $2^k$ の桁が $1$ であるような writer の人数を $U$ とする.$T := \max(0, \lceil \frac{T - U + X}{2} \rceil)$ と更新する.
この方針を数え上げに持ち込みます.上の判定アルゴリズムにおいて $k = i$ まで見た後に $T = j$ となっている $A$ の $2^i$ までの桁としてありうる通り数を $dp[i][j]$ として求める DP が考えられます.
具体的には $U$ を $0$ から $N$ まで全探索し,その場合に $T$ がどう更新されるかを考えれば良いです.
計算量としては $j \leq KX$ として良いので状態数 $O(K^2X)$ で,遷移は $O(N)$ なので $O(NK^2X)$ です.実際には $dp[i][j]=0$ であるところは無視するようにすると $j$ は $O(X)$ となるので $O(NKX)$ で動作します.
これより最終的な $T$ が $i$ となる通り数が何通りかというものを $i$ について求めることができます.したがって,答えが $X$ 未満になる通り数を求めることができます.具体的には総和が $T + X$ 未満となる非負整数列の数え上げの形になります.
よって,答えが \(X\) 未満となる通り数が \(O(NKX)\) で求まるため,全体として \(O(NKX)\) で解けます.
posted:
last update: