https://atcoder.jp/contests/caddi2018
$N$この正の整数で構成される数列が与えられる。これらの整数の中から1つをマイナス2倍する操作を繰り返して数列を単調非減少にするとき、必要な操作の回数の最小値を求めよ。
数列が単調非減少であるときには必ず、ある場所より前はすべて負で、それ以降はすべて正になっている。この境界を全探索すればよい。
数列のある要素から後をすべて正にすると決めたなら、それ以降の数字に操作を奇数回行うことはない(負になるため)、よって、操作の最小単位は4倍になる。ある要素より前をすべて負にすると決めたときも同様で、それ以前の数字に操作を偶数回行うことはない。
実際に4倍していくとオーバーフローするので、DPテーブルを $$DP[i][j]=A[i]{\rm を}j{\rm 回4倍したときにそれ以降を単調非減少にするために必要な4倍操作の数}$$ ととる。1を15回4倍すると1e9を超えるので、1を$N\geq15$回以上4倍したときに、それ以降を単調非減少にするためには$N-1$の場合から以降のすべての数を4倍したものになる。よって、$j\geq16$の部分は記録する必要がなく、$DP[i][15]$から求められる。
逆向きにも同じDPテーブルで計算を行うと、ある位置を負と正の境界にした際に必要な操作回数がO(1)で計算できるようになり、全探索ができる。
与えられる数字が全部正であることを見落としていた。4倍する操作をi回行うとき、$(1\lt \lt 2i)$をかけると速い。