Mitsubachiのメモ

組合せ論をしています

ARC100-E 「Or Plus Max」(700点) 別解

再帰的に解けたので。

問題文

概要

整数列 $A_0,A_1, \cdots , A_{2^N-1}$ について、 $i \neq j$ かつ $i\ or\ j \leq K$ を満たす $i,j$ についての $\max(A_i+A_j)$ を $1 \leq K \leq 2^N-1$ について求めろ。

解法

長さ $2^X$ の数列 $Y$ について $f(Y)$ を上の問題の答えとなる数列の先頭に $0$ を付け加えた長さ $2^X$ の数列とします。

$X=1$ の時 $f(Y) = \left( 0,Y_0+Y_1 \right)$ です。 $X \geq 2$ とします。長さ $2^{X-1}$ の数列 $B,C$ を以下のように定めます。

$B_i = Y_i$
$C_i = \max(Y_i,Y_{2^{X-1}+i})$

$f(Y)$ の前半分は $f(B)$ に帰着できます。後ろ半分について、 $f(Y)_{2^{X-1}+i}=\max(f(Y)_{2^{X-1}+i-1},f(C)_i,Y_i+Y_{2^{X-1}+i})$ です。

よって、長さ $2^X$ の数列について $f$ を求めることは長さ $2^{X-1}$ の数列 $2$ つについて $f$ を求めることに帰着できます。

よって、 $O(N\ 2^N)$ でこの問題が解けました。

実装例