101. 今日解いた問題（2022.04.13）

問題一覧

D - Remainder Reminder (Diff: 1129)
F - Programming Contest (Diff: 1423)
D - Base n (Diff: 1425)

自分の解法など

D - Remainder Reminder

入力例 1 で考えてみます。観察すると、 $K+1 \le b \le N$ であることが分かります。よって、この範囲でそれぞれ $a$ が何通りあるか考えるのがよさそうです。

$b$ で剰余がループすることを考慮して、 $q = \lfloor \frac{N}{b} \rfloor$ 回は全体を取れてそれぞれ $b - K$ 個適切な $a$ が存在します。つまり、 $q(b-K)$ 個足せます。余った分（ $N - q(b-K)$ ）が $K$ 以上ある場合、ここから条件を満たすものだけ足します。

計算量は $O(N)$ です。

F - Programming Contest

DP っぽいですが、 $T \le 10^9$ と制約が大きいので無理です。 $N$ が小さいことに注目すると、全探索っぽいです。 $A_i$ をそれぞれ解く・解かないの全探索が思い浮かびますが、 $N \le 40$ なので $2^N$ 個の状態が出てくることを考えると、これも不可能です。

ここで、探索範囲を限定できないか考えます。2 つの部分集合に分割してそれぞれの総和パターンを算出し、組み合わせから最終的な総和パターンを出してもよいと気付きます。つまり、半分全列挙の問題です。

実際、 $2^{20} \simeq 10^6$ で、部分集合の総和算出はこれを 2 回行うだけなので間に合います。部分集合内の要素に限定した総和集合の算出が $O(2^{N/2})$ です。こうしてできた 2 つの部分集合から元を 1 つずつ選んで足せば、最終的な総和パターンを列挙できます。今回は足して $T$ 以下の最大値を探したいので、どちらかの部分集合をソートしておき、足して $T$ 以下となる最大要素を二分探索で求めればよいです。

以上より、計算量は $O(2^{N/2} \log 2^{N/2})$ 、つまり $O(N \cdot 2^{N/2})$ です。

D - Base n

考察すると、条件を満たす最大の $n$ を $N$ とすると、 $d + 1 \le n \le N$ なる $n$ は全て条件を満たすことが分かります。また、 $X \ge 1$ 、 $M \le 10^{18}$ なので、 $n \le 10^{18}$ です。よって、 $d + 1 \le n \le 10^{18}$ で二分探索して $N$ を求めれば、 $N - d$ が答えになります。計算量は $O(|X| \log M)$ です。