yukicoder No.1460 Max of Min

お題箱より。

No.1460 Max of Min - yukicoder

解法

この問題の解法はいくつかのステップで構成されていて、その1つ1つが覚えておくと有用なテクニックだと思います。順に追っていきましょう。

ステップ1

求めたい値 $A_{N}$ は、与えられた数列の要素に対して $\max$ と $\min$ を取ることを大量に繰り返したものです。要素に対して四則演算などを行うことはありません。

このような問題では二分探索が有用であることがあります。つまりある整数 $x$ に対する「求めたい値は $x$ 以上か？」という判定問題を考え、これを様々な $x$ について繰り返し解くことで求めたい値を特定するという戦略です。

判定問題に落とすメリットは、与えられた要素や計算途中の要素を $x$ 以上かどうかで二値化して考えることができる点です。関数 $f$ を

$a$ が $x$ 以上ならば $f(a) = 1$ 、そうでなければ $f(a) = 0$

と定義します。このとき $\max$ と $\min$ について

$f(\max(a, b))$ は、 $f(a) = 1$ または $f(b) = 1$ のとき $1$ 、そうでないとき $0$
$f(\min(a, b))$ は、 $f(a) = 1$ かつ $f(b) = 1$ のとき $1$ 、そうでないとき $0$

が成立します。そして最終的に $f(A_{N}) = 1$ かどうかを判定すれば良いので、全ての要素を最初から最後まで二値化した状態で考えることができます。

これ以降、数列 $A, B$ の要素は二値化されたものとして扱います。

ステップ2

$A_{i}$ の値を順に決めていく処理について考察します。この処理を視覚的にとらえると次の図のようになります。数列 $B$ をずらして数列 $A$ に重ねていき、もし縦に $1$ が並んだところが存在すれば次の $A$ の要素は $1$ 、そうでなければ $0$ となります。

f:id:betrue12:20210424181547p:plain

ここで数列 $B$ 側の $1$ である要素に注目します。数列 $B$ の後ろから $t$ 番目の要素が $1$ であるとします（ $t$ は $1$ 始まりで数えます）。この $1$ は、

$A$ 側の $1$ である要素 $A_{i}$ と重なったときに、その $t$ 個先にある $A$ の要素 $A_{i+t}$ を $1$ にする能力がある

と考えることができます。

f:id:betrue12:20210424183333p:plain

判定したいのは $A_{N} = 1$ かどうかです。この考え方を用いると、判定問題を次のように書き表すことができます。

与えられた $0 \le i \lt K$ の範囲で $A_{i} = 1$ である要素からスタートして、 $B$ 側の $1$ と重なることで右側に進むことを繰り返し、ちょうど $A_{N}$ に到達できるか？

より正確に定式化するため、次のように集合 $S, T$ を定義します。

与えられた範囲の数列 $A$ について、 $A_{s} = 1$ である整数 $s$ からなる集合を $S$ とする。
与えられた数列 $B$ について、 $B_{K-t} = 1$ である整数 $t$ からなる集合を $T$ とする。

$A_{N} = 1$ かどうかの判定問題は、次のように定式化されます。

集合の要素を1つ選んで、変数の初期値とする。以下の操作を0回以上繰り返すことで、をと一致させることができるか？
- 集合 $T$ の要素を1つ選んで $t$ とする。このとき $x+t \ge K$ である必要がある。 $x$ に $t$ を加算する。

ここで「 $x+t \ge K$ である必要がある」という条件は、処理の過程で $A_{x}$ と $B_{K-t}$ が重なる機会があることに対応しています。

ステップ3

説明を簡単にするため、「 $x+t \ge K$ である必要がある」という条件をいったん無視します。

前ステップで定式化した問題は、個数制限なし部分和問題に初期値の条件が付いたものです。それぞれの値の大きさを確認すると、 $N$ は非常に大きく、 $S, T$ の要素は $K$ 以下なので $1000$ 以下と比較的小さいことが特徴です。

この部分和問題を $O(K^{2})$ で解く方法があります。キーなるアイデアは次の通りです。

大きい値を作る時でも小さい値を大量に足す必要がある。なので小さい値をどれか選んで $m$ として、まず $m$ で割った余りを $N$ と一致させてから、 $m$ を足し続ければ良い。

具体的に解法を説明します。 $T$ の要素のうち、どれでも良いので1つを選んで $m$ とします。 $0 \le r \lt m$ である整数 $r$ について、次の値を考えます。

$D(r) =$ 操作によって作ることができる $x$ の値であって、 $m$ で割った余りが $r$ であるものの最小値

$x$ を $N$ と一致させられる必要十分条件は $D(N \bmod m) \le N$ です。必要性は $D(r)$ の定義から直接分かり、十分性は $x = D(N \bmod m)$ としたあとに $m$ を加算し続けることで $N$ と一致させられることから分かります。

あとは $D(r)$ の求め方です。これを求めるために、次のグラフを構成します。

グラフはそれぞれの $r$ の値に対応する $m$ 個の頂点と、1個の始点を持つ。
始点から、 $S$ の要素を1つ選んで初期値とすることに対応する辺を作る。初期値とする値を $s$ とすると、これは終点が $s \bmod m$ でコストが $s$ の辺である。
始点以外の $m$ 個の頂点から、 $T$ の各要素を加算する操作に対応する辺を作る。辺の始点を $r$ 、加算する値を $t$ とすると、これは終点が $(r+t) \bmod m$ でコストが $t$ の辺である。

$m$ 個の頂点番号は $x$ を $m$ で割った余りに対応し、辺は $x$ に値を加算することに対応しています。そのため $D(r)$ はこのグラフにおける始点からの最短距離として計算することができます。グラフは密になる可能性がありますが、優先度付きキューを使わないダイクストラ法を用いることで $O(K^{2})$ で解けます。

※説明がしやすいので始点を明示的に置きましたが、置かずに $D(r)$ の初期値を $S$ から設定しても構いません。

最後に「 $x+t \ge K$ である必要がある」という条件を考慮します。これを扱うのは面倒なので、最初に $A_{2K-1}$ までの値を愚直に求めて、 $S$ の要素 $s$ を $K \le s \lt 2K$ の範囲で取ってしまうのが楽だと思います。最初から $x \ge K$ として扱うようにすれば条件を気にする必要はありません。ただしこの場合は、 $N$ が小さいときの実装に注意してください。