AtCoder Beginner Contest 336, D : Pyramid

問題文

　https://atcoder.jp/contests/abc336/tasks/abc336_d

問題概要

　正整数 $k$ について，数列 $\langle 1, 2, \dots, k - 1, k, k -1, \dots, 2, 1 \rangle$ を「サイズ $k$ のピラミッド数列」と呼ぶことにする．
　長さ $n$ の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．$A$ に対して，以下の操作の内ひとつを選んで適用することを $0$ 回以上繰り返してピラミッド数列を作ることを考える．

• $A$ の項 $A_i$ を選び，$A_i \leftarrow A_i - 1$ する．
• $A$ の先頭の項を削除する．
• $A$ の末尾の項を削除する．

作ることができるピラミッド数列の内，サイズが最大となるもののサイズはいくらか？　なお，一種類以上のピラミッド数列を作れることが保証される．

制約

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$

解法

　操作を言い換えると，

• 操作後の列の各項は，対応する $A$ の項 $A_i$ 以下の任意の整数になれる．
• 削除操作により任意の連続する部分列を取り出せる．

と言えます．
　以下で「上昇列」「下降列」という言葉を使いますが，問題の性質から本記事では，

• 「上昇列」は先頭が $1$ で公差が $1$ の数列．
• 「下降列」は末尾が $1$ で公差が $-1$ の数列．

という意味で使います．
　ピラミッド数列は中心で左右に分割して，上昇列と下降列の組合せと捉えることができます．そうすると，位置 $i$ を中心とするピラミッド列の最大長とは，

• 位置 $i$ で終わるような上昇列の最大長
• 位置 $i$ で始まるような下降列の最大長

の内小さい方……もとい，大きくない方*1です．この値を求めることができれば，中心となる位置を全て試して最大値をとることで，元の問題を解くことができます．
　上昇列の方について考えてみます．位置 $i$ で終わる上昇列とは，

• 位置 $i$ で始まる長さ $1$ の上昇列．
• 位置 $i - 1$ で終わる上昇列に $A_i$ から作られる値を連結して得られる上昇列．

に分けられます．これを元に，$$L_i := \text{位置 $i$ を末尾とする上昇列の最大長}$$ なる列 $L$ を考えます．$L$ を計算するために，

• 上昇列の長さと上昇列の末尾は等しい．
• 上昇列から一様に値を引いて先頭を適切に切り落とすことで，同じ位置を末尾とするより長さの短い任意の上昇列を作れる．

ということを念頭に置いて漸化式を書くと，
\begin{equation}
L_i = \begin{cases}
1 & \text{($i = 1$)} \\
\min( L_{ i - 1 } + 1, A_i ) & \text{(otherwise)}
\end{cases}
\end{equation}
となります．
　下降列は逆順に見れば上昇列なので同様の考え方ができて，$$R_i := \text{位置 $i$ を先頭とする下降列の最大長}$$ とすれば，
\begin{equation}
R_i = \begin{cases}
1 & \text{($i = n$)} \\
\min( R_{ i + 1 } + 1, A_i ) & \text{(otherwise)}
\end{cases}
\end{equation}
となります．
　あとは各 $i$ について $\min( L_i, R_i )$ の値を計算して，それらの最大値 $\max\limits_{ 1 \leq i \leq n } \min( L_i, R_i )$ を求めれば問題を解くことができます．

計算量について

　まず，上記 $L, R$ を保存しておくために $\Theta( n )$ 空間が必要となります．また，$L, R$ の計算にはそれぞれ $\Theta( n )$ 時間がかかります．最後の最大値を求める処理も $\Theta( n )$ 時間で完了します．入力に $\Theta( n )$ 時間，出力に $O( 1 )$ 時間かかりますが，結局，全体で $\Theta( n )$ 時間となります．

コード (C++)

int main()
{
	IN( int, N );
	VI A( N );
	cin >> A;

	VI L( N ), R( N );
	L[0] = 1;
	REP( i, 1, N )
	{
		L[i] = min( L[ i - 1 ] + 1, A[i] );
	}
	R[ N - 1 ] = 1;
	for ( int i = N - 2; 0 <= i; --i )
	{
		R[i] = min( R[ i + 1 ] + 1, A[i] );
	}

	int res = 0;
	REP( i, N )
	{
		chmax( res, min( L[i], R[i] ) );
	}

	cout << res << endl;

	return 0;
}

コード (Haskell)

main = do
	n <- readInt
	as <- readInts
	let
		ls = f 0 as
		rs = reverse $ f 0 $ reverse as
	print $ maximum $ zipWith min ls rs

f _ [] = []
f p (a:as) = res : f res as
	where
		res = min a $ succ p

*1:両者が等しいときにコーナーケースになるのでこういう言い方になりますね．