Waseda Orientation Programming Contest 2020 J - トレジャーハンター

問題概要
解法
- Med
- Large
コード

問題概要

$N$ 種類のはしごがあり、 $i$ 番目のはしごの長さは $A_{i}$ です。
$0$ 以上 $M$ 以下の値 $P$ で、以下の条件を満たさないものの個数を求めてください。

$N$ 種類のはしごを上手く使い、長さの総和を $P$ にすることができる(ただし、同じはしごは何回でも使用可能、1度も使わなくても可)

$T$ 個のテストケースが与えられるので、全てに答えてください。

Med:

$T = 50$
$1\ \leqq N \leqq 30$
$1 \leqq M, A_{i} \leqq 1000$

Large:

$T = 50$
$1 \leqq N \leqq 30$
$1 \leqq M \leqq 10^{18}$
$1 \leqq A_{i} \leqq 3 \times 10^{4}$

Largeの制約では、最悪でも1分程度で答えが出る想定で、
Python、Javaでは1分以内に全ての答えが出力されることを確認しています。

解法

どの解法でも、1つ1つのテストケースに対して計算し、 $T$ 回繰り返すことを考えます。

Med

$dp[i] =$ 合計距離が $i$ となるような組み合わせができるか(bool値)
として、
初期値: $dp[0] = 0$
遷移: $dp[i] = dp[i] \ or \ dp[i-A_j]$
という計算をすると、 $O(NM)$ で計算可能です。
個数制限無しナップサックを用いたもの。

Large

上記の解法だとメモリ、時間ともに足りません。
$[1,M]$ について全て調べたいですが、それぞれについて考えると、状態数が多くメモリと時間が足りなくなってしまうので、うまく状態数を減らしていくことを考えます(一般に、bool値のDPはより多くの情報を持たせて遷移させることができるはずです、例えば上記のbool値はできるかどうか、だけでなく、ほぼ同じ遷移で使用するはしごの最小個数をそのまま持たせることができます)。
$min(A_i) = X$ とします。
距離 $X$ のはしごのみを適切な回数用いることで、 $X$ の倍数については必ず達成できることは明らかです。
$X$ の倍数ではないときも、ある距離 $D$ が達成できた場合に、その後に距離 $X$ のはしごを繰り返し使うことで、 $D$ 以上の、距離を $X$ で割った余りが $D\%X$ となる地点は全て達成できます。なので、距離を $X$ で割った余りそれぞれについて、可能な最小値を探せば、その最小値未満の値ができない、ということになります。ということで、

$dp[i] =$ $D \% X$ が $i$ になるような合計距離 $D$ の中で、作成可能な最小値

を考えていきます。
$dp[0] = 0,dp[i] = \infty$ で初期化をします。
$dp[i]$ より小さい値の個数をそれぞれの $i$ について計算してあげると、その総和が答えです。ここは $O(X)$ です。

1つめ:01ナップサックに帰着

先ほどのdpについて、個数制限のないナップサック問題を適用することについて考えてみます。
$dp[(i + A_{j}) \% X] = min(dp[(i + A_{j}) \% X],dp[i] + A_{j})$
という遷移になります。
$X = 8$ ,dp配列が $\{0,55,1,3,2,2,1,4\}$ であったときを考えます。
普通、個数制限無しナップサックを考える場合は、dpの添え字0から順番に増やしていきますが、例えば $A_{j} = 12$ だった場合、
次の遷移では
$\{0,55,1,3,2,2,1,4\}$
になります。しかし、添え字5から始めると、
$\{0,14,1,3,2,2,1,4\}$
になります。
( $dp[1] = min(dp[1],dp[(5 + 12)\%8] + 12) = 14$ です)。
このように、始まる添え字によって値が変わり、うまくDPを行うことができません。
このことは、個数制限なし、という条件を、
距離 $D$ のはしごの1個セット、2個セット、4個セット....を用意してあげて、
距離 $D$ のはしご $p$ 個セットを使う/使わない
という2択にすることで、2進数で任意の個数を表現しつつ、うまく処理することができます。

$dp[j][i] = j$ 個目のはしごセットについて使用する/しないを決めたとき、 $D \% X$ が $i$ になるような合計距離 $D$ の中で、作成可能な最小値

とすると、j個目のはしごセットの距離の総和を $H$ として、
$dp[j][(i + H) \% X] = min(dp[j][(i + H) \% X],dp[j][i] + H)$
と遷移することができます。はしごセットは、それぞれのはしごについて、 $A_{j} × 2^{p} \leqq M$ となる $p$ について考えればよいので、 $N \log Y$ 種類で抑えられます(実は、 $N \log X$ で抑えることもできます) 。
よって、 $O(NX \log M)$ で解けました。

2つめ:個数制限なしナップサック

1つめの解法の、個数制限なしナップサックに戻ってみます。
先ほど上手くいかなかったのは、添え字 $0$ から、順番に $1$ ずつ増やしていたからです。
ここを賢く走査することで、個数制限なしナップサックでも解けるようにしてしまいます。
$i$ 種類目のはしごについて、dpの添え字の遷移は、 $GCD(X,A_{i})$ 本のループにわかれます。
例えば、 $X = 10$ , $A_{i} = 14$ のとき、
$0 \rightarrow 4 \rightarrow 8 \rightarrow 2 \rightarrow 6 \rightarrow 0 \ldots$
というループと、
$1 \rightarrow 5 \rightarrow 9 \rightarrow 3 \rightarrow 7 \rightarrow 1 \ldots$
というループにわかれます。
1ずつ添え字を増やして見ていくのではなく、このそれぞれのループについて、個数制限なしナップサックを考えます。
このそれぞれのループについて、現在の最小値を探します。すると、その最小値の部分は、他がどうであれ、今見ている長さ $A_{i}$ のはしごをどれだけ使っても、この最小値が更新されることはありません。
なので、この最小値のインデックス $p$ からスタートして、
$p \rightarrow (p + A_{i})\% X \rightarrow (p + 2 \times A_{i}) \% X \ldots$
と見ていけば、ループを1周するだけでうまく更新できます。最小値を探すのと、更新それぞれで1周ずつすればよく、それぞれのループにある添え字の個数の合計は結局 $X$ になるため、はしご一種類あたり $O(X)$ で計算できます(最小値を探さなくとも、適当な場所から更新をはじめ、2周する、という方法でもいいです)。
これを $N$ 回繰り返すため、 $O(NX)$ でこの問題が解けました。

3つめ:ダイクストラ法

$dp[i] =$ $D \% X$ が $i$ になるような合計距離 $D$ の中で、作成可能な最小値

に戻ります。現在の距離が $D$ の際に、はしご $A_{j}$ を新たに用いたとすると、距離は $D + A_{j}$ に、 $(合計距離) \% X$ は $(D + A_{j}) \% X$ になります。 $dp[i]$ について、添え字 $i$ を頂点番号と考え、頂点 $i$ ではしご $A_{j}$ を使う操作を、コスト $A_{j}$ 、遷移先の頂点が $(i + A_{j}) \% X$ の辺としたグラフを考えることができ、
それぞれの頂点に行く、最短距離を求める問題としてみることができます。
最短距離といえばダイクストラ法です。
$dp[0] = 0$ から、順にはしご $j$ を使う操作による遷移を行い、 $dp[i]$ を埋めることをダイクストラ法を用いて行うと、
頂点数が $X$ 、辺の本数が $(頂点数X×梯子の種類数N) = NX$ 本なので、 $O(NX\log X)$ で解くことができます。

おまけ(Med解以外の想定TLE,MLE解法)

実は、距離が十分に大きい時、
$A_{1}$ ~ $A_{N}$ すべてについての最大公約数を $Y$ とすると、
$Y$ の倍数は全て構築可能、そうでない場合は構築不可能になります。
距離が十分に大きい、というのは、 $max(A_{i})^{2}$ 以上であればOKです。
つまり、 $max(A_{i})^{2}$ までは愚直にMed解法と同じDPで見て、それより大きい部分については、 $Y$ の倍数でない数を数えるだけで、この問題に対して答えることができます。 $O(Nmax(A_{i})^{2})$ です。