SRM456 Div1 hard FunctionalEquation

rngさんの問題表を適当に解いていたら聞いたことあるのが出てきたので解いた. 自力で解けて嬉しい

というか実質初めて解いたhardがこんな重いのになってしまった(平均的難易度を知らないのでなんとも言えない, hardは怖い)

関数方程式という問題名, 一体競技プログラミングとは何だったのか

解説はeditorialがあるはずなので思考過程だけ(正しいものを思いついた順に, 数オリとかやってる/やってた人はもっと賢く解けるのかもしれない)
数式書けないので許してください, メモなので必要十分も適当.



以下ネタバレ





f:Z->Zに注意


まず自由度を減らしたいので色々代入してみる.
f(2f(x) - x + 1) = f(x) + Cのxに2f(x) - x + 1を代入する, 左の式の結果を用いてf(x + 2C) = f(x) + 2Cがわかる. よってx mod 2Cで値が決まる.


少し考えやすくなったが条件が足りなそう. (例えばfが1次関数だと仮定するとf(x) = x + (C - 1) / 2しかだめっぽいし(Cが奇数じゃないとこれもだめ))


試しにf(0) ~ f(2C-1)を文字(a0, a1, ... , a2C-1)で置いてみると, f(x) = ak + (x - k) (k = x mod 2C) = x + (ak - k)
とかける(ak - k = bkと置き直す)

これを与式に代入してみると, f(x + 2bk + 1) = x + bk + C (k = x mod 2C)となる

これx + 2bk + 1が違うx mod 2Cで一緒になったら辛くない??という気分になって

x + 2bk + 1 = y + 2bl + 1 (mod 2C)としてみる. この時 x + bk = y + bl mod 2C も成り立ち, bk = bl, x = yがわかる.

よってk -> k + 1 + 2bk (k=0, ..., 2C-1)の右側もmod 2Cで互いに異なるっぽい.


またここで, l = k + 1 + 2bk mod 2Cとすると,
f(x + 1 + 2bk) = x + bk + Cは, x + 1 + 2bk + bl = x + bk + Cとなって, bk + bl = C - 1 (これは普通の意味での等号)
(x + 1 + 2bk) + 1 + 2bl = x + 2bk + 2 + 2 * (C-1-k) = x+2C (= x mod 2C)で戻ってきた. 思えばx ---- f(x) ---- 2f(x) - xなのであった.

よって0, 2, ..., 2Cと1, 3, ..., 2C - 1で2部グラフと見なせるっぽい.
もうこの対応関係があれば, fは勝手に成り立ちそう.

コストもx[i] mod 2Cで別に考えれば良くて, modを決めればコストが最適化出来るならもうbit dpで計算できる.



ここまで来てコスト計算に苦労してしまった(こっちの方が出来るべきでは...)


2m と2n + 1(0 <= m, n < C)がセットとして, x[i] = 2m or 2n+1 mod 2Cの部分だけ考える.
b2m = tとおく, これらが対応することから2m+2t+1=2n+1 mod 2C つまり2(n-m)=2t mod 2C, n-m=t mod C
(つまりtはn-mからCごとの値を取る)

b2n+1 = C-1-tで,
また|f(x)-y| = |bk-(y-x)| (k = x mod 2C)だから2種類のkについて|bk-t|みたいなのをたくさん足した形になってる

これは三分探索でOK

(editorialに載ってるコスト計算頭良すぎでは)(初期値でsortして絶対値の中身の正負の分かれ目を上手いことする)