ひとり言

Codeforces Round #555 (Div. 3)F. Maximum Balanced Circle

問題概要

長さ $n$ の数列 $a$ が与えられる. この中から任意の個数の数を取り出し, 自由に並び変えたうえで円環状に配置する. このとき, 隣り合う数の絶対値の差が $1$ 以下になるようにしたい.

このような並べ方のうち, 最大のものは何か？

問題へのリンク

制約

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2\times 10^5$

解法

耳 dp 感ないですか？ないですね...

絶対値の差が $1$ 以下なので, $0$ でもいいことに着目します. このことから, 同じところを往復する意味がないです. ( $1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \cdots$ とできるなら, $1 \rightarrow 1 \rightarrow 2 \rightarrow 2 \rightarrow 1 \cdots$ とすればいいです. )

よって, 使用する数字の最小値, 最大値をそれぞれ $l, r$ とすれば, ありうる数字の並びのパターンは以下の通りになることがわかります :

$l$ から出発し, $l \rightarrow l+1 \rightarrow \cdots \rightarrow r \rightarrow r-1 \rightarrow \cdots \rightarrow l+1$ と移動
$i~(l \lt i \lt r)$ から出発し, $i \rightarrow i+1 \rightarrow \cdots \rightarrow r \rightarrow r-1 \rightarrow \cdots \rightarrow l \rightarrow l+1 \rightarrow \cdots \rightarrow i-1$ と移動
$r$ から出発し, $r \rightarrow r-1 \rightarrow \cdots \rightarrow l \rightarrow l+1 \rightarrow \cdots \rightarrow r-1$ と移動

ここで, 数字を連続させていいことを思い出せば, 2. と 3. は1. に帰着できることがわかります. よって, 1. のパターンだけ考えればいいです.

1. のパターンはどのように構築できるでしょうか. 区間 $l, r$ で1. が構築できる条件は, $l, r$ が $1$ 個以上存在し, $l \lt j \lt r$ を満たす $j$ が $2$ 個以上存在していればいいです(間の区間は往復しなければならないことに注意します). よって, $l$ を固定すれば, 自分より大きく, 最初に個数が $1$ 個以下になる数字 $r$ が高速に得られれば, その間の数字はすべて使うことができるのでできる円環の大きさを累積和を用いて計算できます. 自分より大きく最初に個数が $1$ 個以下になる数は, $a_i$ が十分小さいことから前計算で累積的に計算しておきます.

構築は頑張ればできます.

実装

Submission #147403148 - Codeforces