なんか適切な言い換えがパッとできなかった。
公式Editorialにあるとおり「$2B-A-C=X$ として $X=0$ なら等差数列」なので、 考慮すべきが3数から1つの数 $X$ に減る。$X$ に2を足すか1引くかして調整すると考えれば楽。
本番では2数を固定して残り1数を調整した。
3数の初期の並びが $\land$ なら $A$ か $C$ を調整する。どちらを選んでも一緒。
$\lor$ なら $B$ を調整する。その場合 $A,C$ の偶奇が異なればどちらかを1だけ調整する必要がある。
1,2,3
のみからなる数」の和に分割するとき、最小の分割数を求めよ
0
の桁があってはいけないのが厄介。
例えば 412
とかだと、4
は少なくとも2つに分割する必要があるのに、
1
は1つにしか分割できないので、繰り上がりを発生させないといけないことはわかる。
「各桁を何個に分割するか?」を桁毎に考えると、これが広義単調増加になっていればよい。
頭の0は消えるので、桁が下がるにつれ分割数が増えるのはいい。ただ、減るのはアウト。
N 1 4 3 8 ---------------- 分割 1 2 1 3 (例) 2 1 2 1 3 ---------------- 個数 1 2 3 3
なので、各桁、その数を1,2,3
に分割できる最小数と最大数を調べ、その間を広義単調増加になるように選んでいけばよい。
N 1 4 3 8 ---------------- MIN 1 2 1 3 ←4は分割するのに最低2個必要、8は3個必要 MAX 1 4 3 8 個数 1 2 2 3 ←ここが広義単調増加になるように MIN~MAXの間から(なるべく少なく保ちつつ)選ぶ
じゃあ、412
みたいな例はどうするか?
N 4 1 2 ------------ MIN 2 1 1 MAX 4 1 2 2 x ←広義単調増加になるように取れない
繰り下げて、「4 1 2
」ではなく「3 11 2
」として扱えばよい。
更にその次も破綻するので、最終的には「3 10 12
」として扱えばよい。
N 3 10 12 ------------ MIN 1 4 4 MAX 3 10 12 1 4 4
でも、上の桁から分割数を決めていくにしても、 次の桁以降を見てみないと繰り下げればよいかそのままでよいかわからない。
これは、素直に2通り試して小さい方(あるいは破綻しない方)を取ればよい。
再帰関数で実装すると楽。
1つの桁が取り得るパターンは「上から繰り下げてきたか」「下に繰り下げるか」の4パターンしかないので十分少ないが、 メモ化しないと同じケースが何度も呼ばれ、1ケース最大 $2^{17}$ 程度の探索をしてしまうので注意。
あと5分早く思いつきたかった。
まず最小値はともかく、条件を満たす $B,C$ の作り方を考える。
とすると、$B_1$、$C_1$ を上記のように設定した中では $|B_N|$、$|C_N|$ を最小に抑えて構成できる。
A 1 -2 3 -4 5 B 1 1 6 6 15 C 0 -3 -3 -10 -10
ここから、適当な非負整数 $d$ を決め、$B$ 全体を $d$ 減らし、$C$ 全体を $d$ 増やすことをしても条件は満たされたままである。
そんな中で、$\displaystyle \sum_{i=1}^{N}|B_i-d|+|C_i+d|$ を最小化させる $d$ を見つけたい。
絶対値の中身は正負反転させても良いので、$|C_i+d|→|-C_i-d|$ とする。
すると、「全ての $B_i$ と $-C_i$ を $-d$ だけ平行移動させて、絶対値の和を最小化させる」問題になる。
これは、中央値を0とするような移動が答えの1つとなる。(全体を1増やすと、負である個数だけ答えが減り、正である個数だけ答えが増えてしまうので、正と負の個数が釣り合う点が答えとなる)
$B$ と $-C$ をまとめてソートすると、$N$ 番目の数が $d$ となる。後は $\displaystyle \sum_{i=1}^{N}|B_i-d|+|C_i+d|$ をその通りに求めればよい。