G - Leveler MojaMoja

概要

複数の典型的なアルゴリズムを適切に組み合わせて考えることができるかを問う問題です．
一歩づつ，丁寧に考察を進めることで正解できます．

問題原案：tnodino$\>$(改題：achapi, uni_kakurenbo)

略解

一言で言い表すならば 二分探索 in 二分探索 です．

前提として，要素の位置は操作および起伏に関係ありませんから，$A$ がグリッドである必要はありません．

操作によって $A$ の要素の値は減少しないため，$\min A$ を最大でいくらにできるかのみを考えればよいです．
これは「$K$ 回以内の操作によって $\min A$ を $p$ 以上にできるか？」という判定問題を $p$ の値を決め打って二分探索をすることによって求められます．

この判定問題は，「$\min A$ を $p$ 以上にするために必要な，操作回数の最小値 $k$ は $K$ 以下か？」と言い換えることができます．

$k$ の値は，$A$ を昇順にソートして二分探索を行い，累積和を考えることで高速に求められます．

解説

$Ⅰ.$ 問題の整理

操作および起伏に要素の位置は関係ありませんから，$A$ がグリッドである必要はありません．

起伏を減少させるためには，$\max A$ の値を減少させるか，もしくは $\min A$ の値を増加させる必要があります．
しかし操作によって $A$ の要素が減少することはないので，後者のみを考えてよいです．

操作を繰り返して $\min A$ を最大で $P$ にできるとき，この問題の答えは $\max\,\{0,\,\max A - P\}$ となります．

以降 $P$ について考えます．

$Ⅱ.$ $P$ を求める

明らかに，操作回数の上限である $K$ が増えることによって，$P$ が減少することはないです．

したがって，「$K$ 回以内の操作によって $\min A$ を $p$ 以上にできるか？」という判定問題を，$p$ の値を決め打って二分探索を行うことで求めることが可能です．(判定問題の答えが真になる最大の $p$ が $P$ です． )

この判定問題を十分高速に解くことができれば，この方針で正解できそうです．

以降この判定問題について考えます．

$Ⅲ.$ $p$ についての判定問題を言い換える

「$\min A$ を $p$ 以上にするために必要な，操作回数の最小値 $k_p$ は $K$ 以下か？」と言い換えることができます．

この $k_p$ を高速に求めることはできるでしょうか？

以降 $p$ を決めたときの $k_p$ について考えます．

$Ⅲ.$ $p$ から $k_p$ を求める

$A$ のうちで，$p$ 未満である値すべてに対して操作を行って値を増加させる必要があります．

$A$ のうち，$p$ 未満である値 $a$ のそれぞれについて，

• 移動のために $1$ 回
• $p$ まで増加させるために $p - a$ 回

の最低 $p - a + 1$ 回の操作が必要です．

ただし，はじめに Increaser はマス $(1, 1)$ にありますから，$A_{1,1} < p$ の場合は，$k_p$ を $1$ だけ減らしてよいです．

つまり，
$\begin{darray}{ll} E_p &\coloneqq \{\,(i,j) \,| \, A_{i,j} < p\,\} \\ r_p &\coloneqq \begin{dcases} \hspace{0.02em} 1 &\mathrm{if} \> (1, 1) \in E_p \\ \hspace{0.02em} 0 &\mathrm{if} \> (1, 1) \not \in E_p \end{dcases} \end{darray}$
として，
$\begin{darray}{ll} k_p &= \sum_{ (i,j) \in E_p} (p - A_{i,j} + 1) - r_p\\ &= (p + 1)|E_p| - \sum_{(i,j) \in E_p} A_{i,j} - r_p \end{darray}$
と表されます．

したがって，$|E_p|$ および $\sum \limits_{(i,j) \in E_p} A_{i,j}$ の値を高速に求めることができればよいです．

以降これらについて考えます．

$Ⅳ.$ $p$ から $|E_p|$ と $\sum \limits_{(i,j) \in E_p} A_{i,j}$ を求める

$A$ を $1$ つの数列に展開し，昇順にソートしたものを $B = (B_1, B_2, \ldots, B_{N^2})$ として，$B_i < p$ を満たす最大の $i$ を $M_p$ とします．

また，$B$ の累積和 $S$ を次のように定めます．

• $S_0 = 0$
• $S_i = S_{i-1} + B_i \hspace{0.3em} \scriptsize(1 \leq i \leq N^2)$

すると，明らかに $|E_p| = M_p$ であり，$\sum \limits_{(i,j) \in E_p} A_{i,j} = S_{M_p}$ です．

これら $B$ および $S$ はクエリごと不変なので前計算で求めておきます．

以降 $M_p$ を考えます．

$Ⅴ.$ $p$ から $M_p$ を求める

$B$ は単調に増加しますから，$M_p$ は $P$ と同様にして「$B_m < p$ か？」という判定問題を考えて，$m$ の値を決め打って二分探索を行うことにより求めることができます．

$Ⅵ.$ まとめ

最終的な答えを求めるために，$P$ を求めます．
$P$ を求めるために，$p$ についての判定問題を考えます．
この判定問題を解くために $k_p$ の値を求めます．
$k_p$ を求めるために $M_p$ の値を求めます．

$Ⅶ.$ 二分探索の実装について

$M_p$ を求めるために，二分探索を自力で実装する必要はなく，各言語で用意されているライブラリ等が使える場合が多いです．
たとえば C++ ならば std::lower_bound() が，Python ならば bisect.bisect_left() などがあります．

$P$ を求めるための二分探索については，各自で実装するのが一般的です．
探索する $p$ の範囲は，$\min A$ 以上 $\max A$ 以下のものに限っても十分です．

この範囲に絞った場合，$P$ が $\max A$ を超えることがないため，答えを求める際に $0$ との $\max$ をとる必要がなくなります．

ただし実際には，$K$ の値によっては，操作後の $\min A$ の値は，操作前の $\max A$ の値よりも大きくなり得ます．

$Ⅷ.$ 時間計算量の推定

$B$ および $S$ を求めるための前計算に $O(N^2 \log N)$ 時間かかります．

$P$ を求めるために，$O(\log (\max A - \min A))$ 回の判定問題を解く必要があります．
一つの判定問題当たりの時間計算量は，$M$ を求めるための二分探索がボトルネックとなり $O(\log N)$ です．

したがって，全体で $O((N^2 + T\log (\max A - \min A)) \log N)$ 時間です．
これは，この問題の制約下で十分に高速です．

$Ⅸ.$ 発展

$1)$ 類題

• 典型アルゴリズム問題集 $\hspace{0.15em}$ A - 二分探索の練習問題
• ARC 109 $\hspace{0.15em}$ B - log
• ABC 265 $\hspace{0.15em}$ D - Iroha and Haiku (New ABC Edition)
• ABC 271 $\hspace{0.15em}$ C - Manga
• ARC 144 $\hspace{0.15em}$ B - Gift Tax
• ABC 174 $\hspace{0.15em}$ E - Logs
• ABC 241 $\hspace{0.15em}$ D - Sequence Query
• ABC 270 $\hspace{0.15em}$ E - Apple Baskets on Circle
• ABC 174 $\hspace{0.15em}$ E - Logs
• ABC 227 $\hspace{0.15em}$ D - Project Planning

実装例

$\\$

余談

もともと，原案時点では，移動コストが距離に比例する前提で max A の max を求める問題でした．(茶diff?)
そこから，min A の max を求める問題となり，
それが巡回セールスマン問題を含むので NP-Hard だったため，
移動コストから距離の要素を取り除き，(Bit-DP は実装が重そうだったので)
最終的に，max A - min A の min を求める問題となりました．

$A$ がグリッドで与えられることと，Increaser の初期位置が盤面上にあることはこの名残です．

グリッドの方が問題文の表現がしやすいということで，そのままになっています．