yukicoder No.979 Longest Divisor Sequence

• 問題
• AC

一見して端からDPすれば良さそうに見える。つまり、$\operatorname{dp}[x] :=$位置$x$から始まる最長の部分列の長さ、として$\operatorname{dp}[N-1]=1$から逆順に埋めていく方法が考えらえるが、単純に$\operatorname{dp}[x] \leftarrow 1+\max \{\operatorname{dp}[y] : x|yかつx < yかつA_x < A_y\}$と遷移すると間に合わない。

約数の数があまり多くないことを利用すると遷移の数を減らせそう。つまり、$A_y (< A_x)$が$A_x$の約数であるような$y( $$\operatorname{dp}[y] \leftarrow \max (\operatorname{dp}[y], 1 + \operatorname{dp}[x])$$

と遷移したい。ただ、これでは同一の約数がたくさん存在するときに遷移先の候補が減っていない。同一の約数についてはいちばん右のものだけ見ればよいから、

$$\operatorname{stack}[k] := 数列(A_i)中に登場する整数kの位置を降順に保持したスタック$$

を最初に作っておいて、適当にポップしながらスタックの先頭にだけ遷移すればよい。

yukicoder No.980 Fibonacci Convolution Hard

• 問題
• AC

$C_q := a_1a_{q-1} + a_2a_{q-2} + ... +a_{q-1}a_1$とすると、漸化式は次のように書ける:

$$\begin{aligned} C_q & = a_1a_{q-1} + a_2a_{q-2} + ... + a_{q-2}a_2 +a_{q-1}a_1 \\ & = a_1(pa_{q-2} + a_{q-3}) + a_2(pa_{q-3} + a_{q-4}) + ... a_{q-2}(pa_1 + a_0)+ a_{q-1}a_1 \\ & = p(a_1a_{q-2} + ... + a_{q-2}a_1) + (a_1a_{q-3}+...+a_{q-3}a_1) + a_{q-2} \\ & = pC_{q-1}+C_{q-2} + a_{q-2} \end{aligned}$$

ただし$a_0 = 1$とする。

JOI2007 春合宿 - lines

• 問題
• AC

同一の直線は最初に除いておく。以下、$N$本の直線は相異なるとする。

平面走査的に考えてみる。つまり、十分に大きな正数$a$について$x$軸に平行な直線$L: y=a$を用意して、この直線を下に移動しながら領域の数を数える。$y=a$と平行な直線はないとしてよい。^[1] 最初に直線$L$は$N$本の直線と交わっていて、これらに区切られた$N+1$個の領域にまたがっている。$L$を下に移動していくとき、$L$が新たな領域に出会うのは直線の交点に一致した瞬間である。このとき、交点を通る直線が2本なら領域が1つ増え、3本なら2つ増え、一般に$k$本の直線の交点では$k-1$本増えている。

以上の観察より、単に$l_1$から順に直線を追加していき、新しい直線を追加するたびにこれまで追加した各直線と交わる点を（平行でなければ）検出し、同じ交点を検出した回数を数えていけばよい。

$N$本の直線を処理したあと、ある交点$P$をちょうど$2$本の直線が通ったなら、$P$は$1$回数えられ、$3$本なら$1+2 = 3$回数えられる。一般に、$k+1$本の直線の交点は$1+2+...+k = k(k+1)/2$回数えられていて、そこで増えた領域は$k$個になっている。二次方程式を解くと、点$P$が$v$回数えられたならそこで増えた領域は$(-1+\sqrt{1+8v})/2$個である。計算量は${O}(N^2)$。

---

1. あったら、全体を適当に回転させたものを考えればよい。 ↩︎

Code Festival 2014 - eject

• 問題
• AC

$f(x) :=x$回目でONになっている確率とすると、漸化式は

$$\begin{aligned} f(x) & = \sum_k^{x-1} k\text{回目でOFFで、あとはずっとONである確率} \\ & = \sum_k^{x-1}(1-f(k))p(1-p)^{x-k-1} \end{aligned}$$

このままでは間に合わないので差分を計算すると、$f(x)-f(x-1) = p(1-2f(x-1))$になっていて、$f(x) = p + (1-2p)f(x-1)$という線形漸化式が従う。$f(x)-1/2 = (1-2p)(f(x-1) -1/2)$より、$f(x) = 1/2 + (1-2p)^x(f(0)-1/2) = 1/2 + (1-2p)^x\cdot(-1/2)$と表せて、これなら計算できる形になっている。

……と迂遠な導出をしてしまったが、よく見ると自明に$f(x) = p(1-f(x-1)) + (1-p)f(x-1)$だった。直前から求まるかどうかは常に最初に考えるべき。

---

$p=1$の場合に計算誤差が問題になるようだった。(expt -1d0 奇数)は-1になってほしいが、指数が大きいと1になる。手元だと境界はこの辺:

> (expt -1d0 9007199254740991)
-1.0d0
> (expt -1d0 9007199254740993)
1.0d0

前者($=2^{53}-1$)がdouble-floatで正確に表現できる最大の整数なので、そこを超えると精度が落ちるのは明らかとして、そこまではOKなのかは実装次第だが、たぶん普通はOK。

CodeChef Aarambh 2020 - Odd Topic

• 問題
• AC

出現する整数が高々4000種類しかないので、4000個のcompact bit vectorを持ってすべてのクエリに対して累積和で計算する、みたいなムーブを最初にやってしまった。（部分点は取れる。） 結局、バケット法+bitset高速化をした。

簡単のために、数列$a$と$b$の長さは両方$N$とする。$a$と$b$を長さ$B$毎に区切って$k := N/B$個の区間に分解し、さらにそれぞれの区間に対して長さ$4000$のビット配列を保持する。このビット配列を$\alpha_1, ..., \alpha_k, \beta_1, ..., \beta_k$とする。それぞれの区間について、出現する整数の奇遇を数えて

$$\alpha_i[x] := \begin{cases} 1 \qquad (整数xが区間内に奇数個ある場合) \\ 0 \qquad (整数xが区間内に偶数個ある場合) \end{cases}$$

としておく。（$\beta_i$も同様）
各クエリの指定区間に含まれるバケット$\alpha_i, \beta_i$のXORを取って、端の部分は愚直に数えれば、立っているビットの数が答えになる。出現する値の最大値を$A$とすると、計算量は${O}(Q((N/B)\cdot(A/\log A) + B))$。$B= \Theta(\sqrt{NA/\log A})$なら${O}(Q\sqrt{NA/\log A)}$。（$/ \log A$の部分はいわゆるbitset高速化）

コンテスト中は深く考えずに$B=200$としたのだけど、計算量を見ると$\sqrt N$よりは大きいほうがよさそうだったので$B=1000$としてみたら遅くなった。なにか勘違いしてるかも。

---

tmwilliamlinさんの提出を見たら、単純なbitsetの累積和で処理していた。それはそうだった…… ${\mathcal O}((N+Q)A/ \log A)$。

Egorさんは出現する整数のほうを下位5ビットごとに分割して、bitsetなしで通している。

ARC 070 D - No Need

• 問題
• AC

$x$枚目まで見たときに総和が$y$以上になるようなカードの集合の総数を$dp[x][y]$とすると、漸化式は

$$\operatorname{dp}[x][y] = \operatorname{dp}[x-1][y] + \operatorname{dp}[x-1][y-a_{x}]$$

となる。ここで、$N$番目のカードと$i$番目のカードを入れ替えて同じDPをしたものを$\operatorname{dp}_i$とする。$\operatorname{dp}_i$についても同じ漸化式が成立し

$$\operatorname{dp}_i[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i]$$

順番を入れ替えても$N$枚処理すれば同じ結果になるはずだから$\operatorname{dp}[N][y] = \operatorname{dp}_i[N][y]$が成り立つ。したがって

$$\operatorname{dp}[N][y] = \operatorname{dp}_i[N-1][y] + \operatorname{dp}_i[N-1][y-a_i]$$

整理して

$$\operatorname{dp}_i[N-1][y] = \operatorname{dp}[N][y] - \operatorname{dp}_i[N-1][y-a_i]$$

という漸化式が立つ。$i$番目のカードを除いたとき和が$y$以上になるような集合の総数を$f[i][y]$とすると$f[i][y] = \operatorname{dp}_i[N-1][y]$だから

$$f[i][y] = \operatorname{dp}[N][y] - f[i][y-a_i]$$

$\operatorname{dp}$を求めた後、さらに$f$についてDPできる。

カード$i$が不必要
$\Leftrightarrow$ カード$i$を含む和が$K$以上になるような集合と、カード$i$を含まない和が$K$以上になるような集合が一対一対応する
$\Leftrightarrow f[i][K] = \operatorname{dp}[N][K] - f[i][K]$

だから、この等式が成立するような$i$を数えればよい。

$\operatorname{dp}$の値は64ビットに収まらないので、適当にmodをとって扱う。弱衝突耐性があれば十分なので32ビットでよさそう。だめなら複数modを組み合わせればよい。

---

戻すDPを覚えるために復習。

参考: https://sen-comp.hatenablog.com/entry/2019/11/06/121325

ARC 028 D - 注文の多い高橋商店

• 問題
• AC

とりあえず「簡単すぎる」ほうの問題を解く。$\mathrm{dp}[x][y] :=$商品を最初の$x$種類からちょうど$y$個選ぶ方法の総数、とする。$\mathrm{dp}[x][y] = d[x-1][y] + \mathrm{dp}[x-1][y-1] + ... + \mathrm{dp}[x-1][y-a_{x}]$と遷移できるが、これでは間に合わないので累積和を考える。つまり$\mathrm{DP}[x][y] :=$商品を最初の$x$種類から$y$個以下選ぶ方法の総数としたとき、

$$\mathrm{DP}[x][y] = \mathrm{dp}[x][0]+ \mathrm{dp}[x][1] + ... + \mathrm{dp}[x][y]$$ $$\mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{dp}[x][y]$$ $$\mathrm{dp}[x][y] = \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1]$$

が成り立つので、

$$\mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1]$$

という${O}(1)$の遷移を導ける。ここから$y$を一個ずらした漸化式$\mathrm{DP}[x][y-1] = \mathrm{DP}[x][y-2] + \mathrm{DP}[x-1][y-1] - \mathrm{DP}[x-1][y-a_x-2]$を引くと、$\mathrm{dp}$についても同じ形の漸化式が得られる:

$$\mathrm{dp}[x][y] = \mathrm{dp}[x][y-1] + \mathrm{dp}[x-1][y] - \mathrm{dp}[x-1][y-a_x-1]$$

これで簡単なほうの問題が解けた。

さて、ここで$N$番目の商品と$i$番目の商品を入れ替えて同じDPをすることを考える。この配列を$\mathrm{dp}_i$とするとき、$\mathrm{dp}_i$は$\mathrm{dp}$と同じ遷移で求まり、しかも$N$種類の商品を処理すると同じ値になるはずである。つまり、任意の個数$y$について$\mathrm{dp}[N][y] = \mathrm{dp}_i[N][y]$が成り立つ。したがって

$$\mathrm{dp}_i[N][y] = \mathrm{dp}_i[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1]$$

という等式から

$$\mathrm{dp}[N][y] = \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1]$$

が導け、整理すると

$$\mathrm{dp}_i[N-1][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y-a_i-1]$$

となる。$i$番目の商品を除いた場合に全体でちょうど$y$個の商品を選ぶ方法の総数を$f[i][y]$とするとき、$f[i][y] = \mathrm{dp}_i[N-1][y]$であるから、

$$f[i][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + f[i][y-a_i-1]$$

となり、$f$についてDPすればクエリに${O}(1)$で答えられることになる。${O}(NM + Q)$。

---

戻すDPというらしい。

参考:
http://sigma425.hatenablog.com/entry/2015/07/31/121439

EDPC X - Tower

• 問題
• AC

問題文と制約を見て${O}(N \max s_i)$で解くしかないという気持ちになる。順番が固定されていないが、固定されていないと難しすぎるのでその方法を探す。

丈夫さについても重さについても、大きいブロックは下に置いたほうが良いはずなので、まずは$s_i+w_i$で降順にソートするという案を思いつく。実際、それでよいことが証明できる。有効なタワーが与えられたとし、丈夫さと重さが下のブロックから$(s'_1, w'_1), (s'_2, w'_2),..., (s'_k, w'_k)$になっているとする。隣り合うブロックで$s'_i + w'_i \le s'_{i+1} + w'_{i+1}$が成り立つペアがあったとき、ブロック$i$とブロック$i+1$を入れ替えても有効なタワーのままであることが示せれば十分である。

ブロック$i$と$i+1$を入れ替えたとき、$1, ..., i-1$番目と$i+2, ..., k$番目のブロックにかかる重さは変わらず、$i$番目だったブロックにかかる重さは減るので、$i+1$番目だったブロックについてだけ考えればよい。このブロックに以前掛かっていた重さを$G$とすると、新しい配置で掛かる重さは$G+w'_i$になる。ところで$i$番目だったブロックは丈夫さ$s'_i$で重さ$G+w'_{i+1}$に耐えていたので$s'_i - w'_{i+1} \ge G$が成り立つ。$s'_i + w'_i \le s'_{i+1} + w'_{i+1}$から$s'_{i+1} - w'_i \ge s'_i - w'_{i+1} \ge G$が従い、丈夫さ$s'_{i+1}$で$G+w'_i$に耐えられることがわかる。従って、ブロック$i$と$i+1$を入れ替えてもタワーは有効である。$\square$

$s_i+w_i$の降順に並んだタワーだけ考えればよいことがわかったので、あとは端からDPすればよい。$\operatorname{dp}[x][y] :=$ ブロック$1, 2, ..., x$から作れて、耐えられる重さが$y$であるようなタワーの価値の最大値、とする。

$$\operatorname{dp}[x+1][\min(y-w_{x+1}, s_{x+1})] \leftarrow \max (*, \operatorname{dp}[x][y] + v_{x+1})$$ $$\operatorname{dp}[x+1][y] \leftarrow \max(*, \operatorname{dp}[x][y])$$

と遷移すればよい。（$*$は左辺）

CODE FESTIVAL 2016 Relay H - 早起き

• 問題
• AC

$T=0$の場合に高橋君が起きる時刻を$c_1, c_2, ..., c_N$とする。数列$(c_i)$全体に定数を足して（または引いて）、$\mod 86400$で$\{ 0, 1, ..., 10800\}$に含まれるような$c_i$の数を最大化すればよい。ところで、$(c_i)$の代わりに後者に定数を足すと考えてもよい。つまり、$c_i$を$\mod 86400$で分類した時に、$[x, x+10800]$に含まれる$c_i$の数を（$x$を動かして）最大化する問題と考えられる。調べる範囲は$x=0, 1, ..., 86399$でよく、累積和で処理しておけば各ステップは${O}(1)$で済む。

第一回 アルゴリズム実技検定

• アーカイブ
• 提出

リアルタイム受験した。3時間58分で全完。普段のABCよりさらに典型寄りという感じがした。

F

ソートするだけなのだが、計算量がすぐにはわからなかった。例えば単語が$k$個あるとしてヒープソートすると、新しい単語$w_i$をヒープに挿入するたびに最悪${O}(\log k)$回の単語比較が必要で、比較にかかる時間は自身の長さで抑えられるから全体で${O}((|w_1| + ... + |w_k|)\log k) \subseteq {O}(N\log N)$とわかる。最悪計算量が${O}(N \log N)$であるような比較ソート一般でもそうなるとは思うけど、よくわからない。

H

平衡二分木でシミュレーションできるのでコンテスト中はそうした。

コンテストが終わったあと考えていたが、奇数番目カードの最小値、全体の最小値、奇数番目カードのオフセット、全体のオフセットの4つを保持すれば配列だけでシミュレーションできる。

I

ABC 142 - Eとだいたい同じ問題。ゼータ変換から部分集合に関するDP(${O}(3^N+M)$)をやろうとして、これは普通のbitDP (${O}(2^NM)$)で解けることを思い出した。

J

任意の始点から与えられた3点に向かう最小費用流を求めるイメージが浮かんだが、それはなさそう。→そもそも、フローが流れる辺が重複した時にコストが2回数えられるのはまずいのでは→いや、その時は別の始点から重複なしで流したのと同じ形になっているので、最小値には影響しないはず→だったら各点から3点への最短距離を求めれば十分では？→全点からダイクストラ。

よく考えると、全点からダイクストラの代わりに3点からダイクストラで十分だった。

N

各$l, r$について、$[l-C, l]$あるいは$[r, r+C]$を空ける場合のコストを求めて比較すればよい。累積和でできるけど、これも遅延伝搬付き平衡二分木で楽をした。

O

$f(x) :=$目$x$を出したあとの操作回数の期待値、として漸化式を書き出したあと、どう更新するか迷った。$x$が最大のとき$f(x) = 0$で、$x$が小さくなるにつれて有効な項が単調に増えていくので、降順に更新していくのがよさそう。特にデータ構造は必要ないのだが、なぜかBITが必要だと思ってしまった。

---

問題が公開されたのでもう一回解きなおしたら、全体的にかなり手間取った。当日は運がよかっただけかもしれない。

CodeChef January Challenge 2020 - Chefina and Prefix Suffix Sums

• 問題
• AC

$0+suf_N = pre_1 + suf_{N-1} = pre_2+suf_{N-2} = ... = pre_N + 0$であることに注目する。この等式より、$pre_n = suf_n$は$入力全体の和/(N+1)$と一致しなければならない。この数が入力の中に2つなければ答えは$0$である。

さて、この2数を除いた$2(N-1)$個の数の中から残りを埋めることになる。まず、$a_i + b_i = S$になるような数の組み合わせを入力から探す。これらを

$$\{a_1, b_1\}, \{a_2, b_2\}, ..., \{a_k, b_k\}$$

とするとき、すべての$p$について$a_p$と$b_p$は入力の中に必ず同数存在しなければならない。逆に同数あれば、$pre_i = a_p$のとき$suf_{N-i} = b_p$（$pre_i = b_p$のとき$suf_{N-i} = a_p$）のように埋めていけば有効な列ができることになる。

$\{a_1, b_1\}, \{a_2, b_2\}, ..., \{a_k, b_k\}$がそれぞれ$c_1, ..., c_k$ペアあるとわかったら、あとは$\{a_1, b_1\}$から順に$N-1$個の位置を埋めていけばよい。つまり、

$$\binom{N-1}{c_1}2^{c_1} \cdot \binom{N-1-c_1}{c_2}2^{c_2} \cdot ... \cdot \binom{N-1-c_1-...-c_{k-1}}{c_k}2^{c_k}$$

が答えになる。$N-1$箇所の空きから$c_1$個選んで、さらに$a_1$と$b_1$のどちらを置くか選んで…… というイメージ。$a_i = b_i$のケースは$2$掛けがないので注意すること。

---

冒頭の事実に気づくのになんと二日かかってしまった。

CodeChef January Challenge 2020 - English

• 問題
• AC

まず、接頭辞と接尾辞を両方考慮するという設定は、接頭辞だけの設定に直せる。アルファベットが$26 \times 26$種類あることにして、単語とその反転を合わせて扱えばよい。例えばpoemなら$(p, m)(o, e)(e, o)(m, p)$という列だと思えばよい。

さて、本題は重みつきマッチングだが、一般のマッチングアルゴリズムでは無理なのでgreedyを探す。まず思いつくのはスコアの高いペアからマッチングしていくことで、実はこれでよいことがわかる:

単語$x, y$の最長共通接頭辞の長さを$f(x,y)$とする。また、4つの単語$a, b, c, d$が与えられたとし、$f$が最大になる組み合わせが$\{a, b\}$だとする。このとき、接頭辞の性質により

• $f(c, d) \ge \min(f(c, a), f(a, b), f(b, d))$

が成り立ち、$f(c, d) \ge f(c, a), f(c, d) \ge f(a, b), f(c, d) \ge f(b, d)$のどれを仮定しても$f(a, b)^2 + f(c, d)^2 \ge f(a, c)^2 + f(b, d)^2$が成り立つので$\{a, b\}, \{c, d\}$と組み合わせるのがもっともスコアが高くなる。

したがって、マッチングとそれに含まれる2つのペア$\{u, v\}, \{x, y\}$が与えられた時、4点の中でもっともスコアが高くなる辺を優先してマッチングをつなぎかえても全体のスコアは下がらない。このことより、最大スコアを達成するマッチングは上述のgreedyで得られることが示された。$\square$

実装をどうするかで迷ったが、Trieにすべての単語を登録した上で、DFSして深いものから順にマッチングを決めていった。

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes

• 問題
• AC

求めるのは$(N-1)!$通りの移動に関する距離の総和である。

$f(p, q) := x_p$から$x_q$への移動による距離の総和、とする。この移動が起こるのは、スライム${p+1}, ..., {q-1}$が自由な順番で選ばれ、そのあとで$p$が選ばれ、さらにそのあとで$q$が選ばれるケースである。この選び方を数えると、$N-1$箇所の中から$q-p+1$箇所を選び、その中の始めの$q-p-1$箇所にスライム$p+1, ..., q-1$を自由な順番で配置し、末尾の2箇所にスライム$p, q$を配置し、残った$N-1-(q-p+1)$箇所に残りのスライムを自由に並べればよい。つまり、

$$\begin{aligned} f(p, q) & = \binom{N-1}{q-p+1}(q-p-1)!(N-1-(q-p+1))! \times (x_q-x_p)\\ & = \frac{(N-1)!}{(q-p+1)(q-p)}(x_q-x_p) \end{aligned}$$

ただし、$q = N$の場合はスライム$q$が選ばれないので

$$\begin{aligned} f(p, q) & = \binom{N-1}{N-p}(N-p-1)!(N-1-(N-p))! \times (x_N - x_p) \\ & =\frac{(N-1)!}{(q-p)}(x_N - x_p) \end{aligned}$$

となる。$f$の総和を単純に計算すれば部分点が取れる。

上の式で$x_q-x_p$に掛かる係数は幅$q-p$のみによって決まっているので、同じ幅について（$q \neq N$の場合に関して）整理してみる:

$$\begin{aligned} & \sum_{p=1}^{N-1}\sum_{q=p}^{N-1}f(p, q)/(N-1)! \\ = &\frac{1}{2\cdot 1}(x_2-x_1) + ... + \frac{1}{2\cdot 1}(x_{N-1}- x_{N-2})\\ & + \frac{1}{3\cdot 2}(x_3-x_1) + ... + \frac{1}{3\cdot 2}(x_{N-1}- x_{N-3}) \\ & + .. \\ & + \frac{1}{(N-1)\cdot (N-2)}(x_{N-1}-x_1) \\ = &\frac{1}{2\cdot 1} \bigl( (x_2+x_3 + ... + x_{N-1}) - (x_{1}+x_2 + ... +x_{N-2}) \bigr )\\ & + \frac{1}{3\cdot 2} \bigl( (x_3+x_4 + ... + x_{N-1}) - (x_1 + x_2 + ... + x_{N-3}) \bigr) \\ & + ... \\ & + \frac{1}{(N-1) \cdot (N-2)}(x_{N-1} - x_1) \\ \end{aligned}$$

（$(N-1)$!は共通なので除いて整理した。） これは累積和で処理できる形になっている。

---

満点に達するのに3時間かかった。解説の方針のほうが確かにずっと明快だけれど、上の整理くらいはさっさとできるようになりたい。

いろはちゃんコンテスト Day 2 J - ヌクレオチド

• 問題
• AC

$N$が偶数の場合を考える。左右の$N/2$文字をそれぞれ$L, R$とすると$R$は$L$の反転になる。つまり、$L$の中で転倒$A_i > A_j, i < j$が起こっているとき、$R$の対応する位置では$A_{i'} < A_{j'}$となる。$L,R$をあわせると、$A_i = A_j$である$i, j$以外は1回ずつ転倒を数えていいことになる。つまり、$L$に$0$が$z$個含まれるとすると、$A_i = A_j = 0$なる組が$\binom{z}{2}$個、$A_i = A_j = 1$なる組が$\binom{N/2-z}{2}$個含まれるので、$L$の並べ方全体からこれらを引けば（$L$内と$R$内の）転倒の総数が$\binom{N/2}{z}-\binom{z}{2}-\binom{N/2-z}{2}$と数えられる。あとは$L$内の$1$と$R$内の$0$による転倒を足して

$$\binom{N/2}{z}-\binom{z}{2}-\binom{N/2-z}{2} + (n/2-z)z = K$$

$L$に$0$が$z$個含まれるときにはこの等式が成立していなければならないことになる。式を整理すると$2z^2 -Nz + K = 0$となって、この二次方程式の整数解は高々2つなので、2つの解について数列の総数を求めればよい: $\binom{N/2}{z_1} + \binom{N/2}{z_2}$

$N$が奇数の場合についても、例えば中央が$0$と決めて同様の議論をすればよい。（対称性により、中央が$1$の場合も同数の列がある。）

JOI2014 春合宿 - 歴史の研究

• 問題
• AC

オフラインなのでMo's algorithmが適用できる。つまり、平衡二分木（あるいはセグメント木+座標圧縮）などを用意して、区間$[l, r]$を$[l, r+1]$に伸ばすときは$dp[X_{r+1}] += X_{r+1}$と更新して、$[l, r]$を$[l, r-1]$に縮めるときは$dp[X_r] -= X_r$とすればよい。$[l, r]$から$[l-1, r]$、$[l, r]$から$[l+1, r]$なども同様である。それぞれのクエリについて$\max dp$が答えになっている。${O}(N \sqrt{Q} \log N)$。

---

平衡二分木を使ったらTLEしてしばらく放置していたが、よく考えると全体の$\max$にしか興味がないので（優先度の変更可能な）優先度付きキューを使えば十分なのを思い出した。えびちゃんさんの記事にやり方が載っているので、書いたら通った。

CADDi 2018 E - Negative Doubling

• 問題
• AC

完成した数列はどこかで符号がマイナスからプラスに切り替わることに注目する。$N=5$なら、

• $+++++$
• $-++++$
• $--+++$
• $---++$
• $----+$
• $-----$

の6通りがありえる。たとえば$A_3$で符号が切り替わると決めてしまうと、あとは$A_3, A_4, A_5$の好きな数に好きなだけ4を掛けて単調非減少にして、$A_2, A_1$にも4を掛けて単調非減少にして、最後に$A_2, A_1$に$-2$を掛ければ全体として単調非減少になっている。

そこで、$f^+(x) := A_x, A_{x+1}, ..., A_{N}$を単調非減少にするための最小コスト、と定める。おそらく$f^+(N+1) = f^+(N) = 0$からスタートして$x=N-1, N-2, ..$と順に$f^+(x)$の値を求めていけそう。さらに、$f^-(x) := A_{x}, A_{x-1},..., A_{1}$を単調非減少ににするための最小コスト、とすれば$(f^-(x) + x) + f^+(x+1)$の最小値が答えになる。（$+x$は$-2$を掛けるぶんのコスト。）

さて、$f^+$を求める具体的な方法が問題になる。この手順が与えられれば、$f^-$は同じ方法を逆順の配列に適用するだけでよい。先に述べた通り、$f^+(N+1)=0$からスタートして降りていくことにする。とりあえず、正しくないがシンプルな方針から:

1. $A_x \le A_{x+1}$なら$f(x) := f(x+1)$。
2. $A_x > A_{x+1}$なら$A_{x+1}$に何回か$4$を掛けて非減少になるようにする。つまり、$A_x \le 4^k A_{x+1}$となるような最小の$k$を求めて、以降の$A_{x+2}, ..., A_{N}$にも同じだけ$4$を掛ける。このとき、$f(x) := f(x+1) + 2k(N-x)$となる。

この方法の問題点は入力例1に適用してみればわかる:

4
3 1 4 1

$f(5) = 0, f(4) = 0, f(3) = 2, f(2) = 2$までは正しく求まるが、$A_1=3$を処理する際に$4$を掛ける必要があるのは$A_2=1$だけで、$A_3, A_4$はそのままでいいことを見落としていた。つまり、$A_2, A_3$の間にはすでに$4$倍の差があるので、一回分の$4$掛けに限っては$A_2$で吸収されてしまうことになる。一般に、$A_{x+1}$が$A_x$の$4^k$倍以上である時、$k$回ぶんの$4$掛けは$A_x$に吸収されて$A_{x+1}$以降には影響しない。この$k$を$x$の 容量 と呼ぶことにする。上の手順で降りていくとき、各$A_x$について（容量が正なら）$(x, 容量)$のペアをスタックに積んでいくことにする。

1. $A_x \le A_{x+1}$なら$f(x) := f(x+1)$。$x$の容量が正ならスタックに$(x, 容量)$を積む。
2. $A_x > A_{x+1}$なら$A_{x+1}$に何回か$4$を掛けて非減少になるようにする。つまり、$A_x \le 4^k A_{x+1}$となるような最小の$k$を求める。スタックの先頭が$(y, 容量)$になっているとき、$A_{x+1}, ..., A_{y}$に$\min (容量, k)$だけ$4$を掛ける。このとき、操作回数は$2\min(k, 容量)(y-x)$だけ増えるが、容量が$k$より小さい場合はさらにスタックをポップしながら$k$回の$4$掛けが終わるまで繰り返す。

各インデックスについて、スタックへのpushとpopは1回しか行われないので、スタック操作は全体で${O}(N)$になっている。