ABC 226 F - Score of Permutations

• 問題

$F(M) =$長さ$N$の順列で、すべてのサイクルの長さが$M$の約数であるようなものの数 $f(m)=$長さ$N$の順列で、サイクルの長さのLCMが$m$であるようなものの数

とするとき、求める数は$N$の分割のLCMとして得られるようなすべての$m$について$f(m)m^K$の総和を取ったものに等しい。

$F(M) = \sum_{m | M} f(m)$であり、$f$は$F$のメビウス反転として計算できる。また、$N$の分割のLCMの最大値はランダウ関数$g(N)$として知られていて、OEISによると$g(50) = 180180$なので、個々の$F(M)$を高速に計算できればよさそう。

$F(M)$は単純なDPで求まる。$\operatorname{dp}[x] = 1, 2, ..., N$から$x$個使って任意個数の長さが$M$の約数であるようなサイクルを作る場合の数、とするとき、$M$の各約数$m ( \le N)$について

$$ \operatorname{dp}[x+m] \mathrm{{+}{=}} (m-1)! \binom{N-x-1}{m-1}\operatorname{dp}[x] $$

と遷移すればよい。$(m-1)!$は長さ$m$のサイクルの総数であり、$\binom{N-x-1}{m-1}$はまだ使っていない$N-x$個の数から（完全な数え上げをするために）必ず最小の数は選ぶとして残りの$m-1$個を自由に選ぶことに対応している。計算量は${O}((N^2 +\log K)g(N))$。^[1]

また、FPSで考えることもできる。$M$の約数だけに限って各長さのサイクルの総数を数えたEGFを$\mathcal D_M(x)$とするとき、$\mathcal D_M(x)=\sum_{m | M}(m-1)!x^m/m! = \sum_{m|M}x^m/m$である。このとき、$F(M) = [x^N/N!]\exp(\mathcal D_M(x))$である。^[2] FFTを使うと計算量は${O}((N\log N + \log K) g(N))$。

---

解説を見ると、LCMごとにまとめなくてもすべての分割を試せるらしい。確かに。

---

1. 実際には$1, 2, ..., g(N)$の約数で$N$以下であるものの総数が問題になる。これが${o}(N^2)$であればもっとよい評価ができることになるけれど、よくわからなかった。 ↩︎

2. 仮に「箱」が区別できる設定だったら単にEGFの掛け算をすればいいので$[x^n/n!]\sum_{n \ge 1}\mathcal D_M(x)^n$でよくて、箱の区別を無くすために各項を$n!$で割ると$\sum_{n \ge 1}\mathcal D_M(x)^n/n! = \exp(\mathcal D_M(x))$になる。 ↩︎

ACL Beginner Contest F - Heights and Pairs

• 問題
• AC

$h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。

身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペアを作る場合の数は$\binom{i}{2j}p_j$である。$F(x) = \prod_h \sum_j \binom{a_h}{2j}p_j x^{j}$とすると、$F(x)$の$x^k$の係数$[x^k]F(x)$は$2N$人から身長が同じであるような$k$ペアを作る場合の数に等しい。このとき、残った人、つまり$2(N-k)$人でペアを作る場合の数は$p_{N-k}$通りであり、あとは包除で$\sum_k(-1)^kp_{N-k}([x^k]F(x))$通りと求まる。

$(2N-1)!!$について

$2N$人に$1, 2, ..., 2N$という番号を振ってこの順に並べ、二人ずつ取り除いていくとする。この際、ペアのうちの一人目は必ずその時点で番号が最小の人を選ぶ、としておくと完全な数え上げができる。一人目には$2N-1$通りの人がマッチできて、二人目には$2N-3$通りの人がマッチできて、……となるので二重階乗の記号を使うと$(2N-1)!!$と表せる。

別の考え方もできる。$2N$人を自由な順番で一列に並べて、隣り合う二人をくっつけて$N$ペアを作ることにする。並べ方は$(2N)!$通りあるが、二人組の内の順番は考慮しないので$2^N$で割る必要がある。さらに、$N$ペアの順番も考慮しないので$N!$で割って$(2N)!/(2^N N!)$と求まる。これらは二重階乗の公式も与えている:

$$ (2N-1)!! = \frac{(2N)!}{2^N N!} $$

エイシング プログラミングコンテスト 2020 F - Two Snuke

• 問題

$2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delta k\Delta e$の総和を取る問題。

$d = N - (\Delta s + \Delta n + \Delta u + \Delta k + \Delta e )$とするとき、$\Delta s\Delta n\Delta u\Delta k\Delta e$は$s_1+n_1+u_1+k_1+e_1 \le d/2$の非負整数解の数だけ足される。これは$\binom{\lfloor d/2 \rfloor)+5}{5}$通りだから、求める数は

$$ \sum_{d_1+d_2+d_3+d_4+d_5 + d = N}\binom{\lfloor d/2 \rfloor+5}{5}d_1d_2d_3d_4d_5 $$

に等しい。FPSで考えるなら、$\sum_n nx^n = x/(1-x)^2$を5乗して$\sum_{i} \binom{\lfloor i/2 \rfloor +5}{5}x^{i}$という謎の級数を掛けると、$x^N$の係数が求める数である。後者にBerlekamp-Massey法を適用してみると21次の多項式を分母とする有理式が出てくるので、$x^N$の係数はBostan-Mori法で求まる。

---

そもそも一般に$\lfloor i/2 \rfloor$の多項式を係数にするFPSが有理べき級数になるのかどうかとか、基本的なことがよくわかっていなかった。

与えられたFPS$f(x)$の偶数項、奇数項がそれぞれ有理べき級数$g(x), h(x)$の偶数項、奇数項と一致しているなら、$g$の(0-basedで)偶数項だけ抜き出したもの$(g(x)+g(-x))/2$と$h$の奇数項だけ抜き出したもの$(h(x)-h(-x))/2$を足せば$f(x)$になるので、確かに有理べき級数になる。一般に$\lfloor i/k \rfloor$の多項式を係数とするFPSについても、$1$の$k$乗根を考えれば同じことが言える。

一般化すると、次の性質を満たす$f(x) = \sum_n a_n x^n$は有理べき級数と言える:

$M$個の有理べき級数$f_k(x) = \sum_n b_{k, n}x^n \ (k=0, 1, ..., M-1)$と$N \in \mathbb N$が存在して、$n \ge N$ならば$a_n = b_{n \bmod M, n}$。

HackerEarth - Connected Permutations

• 問題
• AC

求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n+1$は$k$箇所に挿入可能なので$a_{n+1} =\sum_{k=1}^{n}ka_k(n-k)! = \sum_{k=0}^nka_k(n-k)!$。$a_0=0, a_1=1$としてオンラインFFTすると${O}(N \log^2 N)$で解ける。

CodeChef SnackDown 2021 Online Qualifiers - Minimise Difference

• 問題
• AC

問題: 無向グラフが与えられる。出次数の最大値が最小であるようなacyclic orientationを求めよ。

出次数が$D$以下であるacyclic orientationが存在するかどうかの判定問題が解ければよい。判定問題は次のように解ける:

まだ選んでいない頂点の中でトポロジカル順序で先頭にする頂点$v$を自由に選ぶ。この$v$の次数は$D$以下でなければならず、そのような頂点が存在しなければ判定はNOである。存在する場合、$v$から伸びているすべての辺を削除する。以上を頂点の数だけ繰り返す。実装はキューで${O}(N)$でできる。

エクサウィザーズプログラミングコンテスト2021 (ABC 222) G - 222

• 問題
• 提出

与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatrix}, v= \begin{bmatrix} 0 \\ 1\end{bmatrix}$とするとき、$a_k$は$M^k v$の第一成分に等しい。従って、問題は$v = M^kv$であるような最小の正整数$k$を求めることと言い換えられる。

この問題はbaby-step giant-stepで解ける。$B= \lceil \sqrt K \rceil$とする。$a_0, a_1, a_2, ..., a_{B-1}$について$\mod K$での値をmapのキー、添字をmapの値として保持しておく。（キーが重複する場合、そこでサイクルに入るので、それまでに$0$が見つかっていなければ打ち切ってよい。） $k= iB-j$, $j \in \{0, 1, ..., B-1\}$とする時、$v = M^kv$が成り立つためには$M^j v = M^{iH}v$が成り立つ必要がある。したがって、$i=1, 2, ..., B$について$M^{iB}v$を計算して$a_{iB}$を求め。この値が先に作ったマップに入っていれば対応する添字$j$を取り出すと$k=iB-j$が答えの候補になる。ただし、$M$は正則とは限らないので、$M^j v = M^{iB}v$は必要条件でしかない。つまり、$a_{iB-j} \mod K$が必ず$0$になるわけではない。実際に$M^{iB-j}v$を計算して確認する必要がある。

ハッシュテーブルを使った場合の期待計算量は${O}(\sqrt K)$。

ABC 221 H - Count Multiset

• 問題
• AC

分割数っぽい数え上げなので分割数っぽいDPを考える。

まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて得られ、分割の中に1を含むものは$n-1$の$k-1$分割に1を付加すれば得られるのだった。漸化式で表すと

$$ P(n, k) = P(n-k, k) + P(n-1, k-1) $$

このDPを、同じ数を$M$個より多くは含まないという制約（以下、単に制約と呼ぶ）に合うように修正することを考える。制約付きの分割の総数を$P'(n, k)$とする。

上の遷移の一つ目の項、つまり分割の中に1を含まないものを$n-k$の$k$分割のすべての項を$1$増加させて得る場合については、制約はそのまま守られるのでこのままでよさそう。一方、二つ目の項、つまり、分割の中に1を含むものを数えたい場合、このままだと1を$M+1$個含むものも数えてしまうことになるので、これを除きたい。

$n$の$k$分割で$1$をちょうど$M+1$個含み、他は制約を満たしているようなものの総数 = $n-(M+1)$の$k-(M+1)$分割で1を含まず、かつ制約を満たしているようなものの総数 = $n-(M+1)- (k-(M+1))$、つまり$n-k$の$k-(M+1)$分割で、制約を満たしているようなものの総数

と言い換えると、最後の量は$P'(n-k, k-(M+1))$に等しいので、漸化式は

$$ P'(n, k) = P'(n-k, k) + P'(n-1, k-1) - P'(n-k, k-(M+1)) $$

となる。

---

スターリング数っぽい数え上げがスターリング数っぽいDPでできる、はけっこう見るけど、分割数っぽい数え上げではうまくいく問題を見た記憶がなくて、遷移を考え始めるまでに時間がかかった……が、例えばJOI 2009 予選 F - ビンゴ がそうだったのを思い出した。

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

満点だった。

L - K番目の絶対値

総和の絶対値が$D$以下であるような連続部分列を数える問題が解ければよさそう。累積和$S_i = A_1 + ... + A_i$上で言い換えると各$i$について$|S_i-S_j| \le D$であるような$j < i$を数えればよく、これは$S_0, S_1, ..., S_{i-1}$の中で$[S_i-D, S_i+D]$に含まれるようなものを数えることに等しい。数え上げを${O}(N \log N)$で解くと、全体で${O}(N \log N \log \sum_i |A_i|)$。

順序対を数えることにすれば尺取りでできる。確かに。

M - バランス

SoundHound Inc. Programming Contest 2018 Masters Tournament E - + Graph

O - 色分けトーナメント

• トーナメントは$2 \cdot 2^N-1$頂点の完全二分木とすると、制約$(W_i, L_i)$は$W_i$と$L_i$のLCAまで$W_i$と$L_i$が勝ち上がって$W_i$が勝つこととみなせる。
• ある選手を青に塗ると決めても赤に塗ると決めても有効な塗り方は同数ある。（どの有効な塗り方についても、すべての色を反転したものが有効な塗り方であるため。）

$\operatorname{dp}_v[x] =$頂点$v$を根とする部分木に属する左から$x$番目の選手の色を決め打った時に、部分木$v$に属する選手の塗り方で（部分木$v$に含まれる制約を満たし、かつ）$v$が勝ち上がるようなものの総数、とする。$\operatorname{dp}_v$は$v$の子を$c_1, c_2$として$\operatorname{dp}_{c_1}, \operatorname{dp}_{c_2}$から線形で作れるので、下から処理していけばよい。根に関する$\operatorname{dp}$の総和を2倍したものが答えになる。

各深さの$\operatorname{dp}$の長さの総和はちょうど$2^N$になるので、全体の計算量は${O}(N 2^N + M)$。

日本橋ハーフマラソン 2021 増刊号 A - 農場王X

• 問題
• 最終提出

評価関数を作ってビームサーチした。

前提

収穫機を買うのをどこでやめるか問題はしばらく考えずに、収穫機も資金に換算したスコアで物事を考えることにした。

評価関数

収穫機を設置/撤去する場所の持つべき望ましい性質を列挙して、それらの組み合わせで評価関数を作る。評価はマス毎に行い、価値の高いマスに収穫機を設置して価値の低いマスから収穫機を撤去する貪欲法を前提とする。また、理想的には、収穫機のあるマスの価値の総和を取ると盤面の価値になっていてほしい。

以下の評価関数に従って貪欲法をするとして、収穫機を買うのを止めるタイミングを全探索すると2.6億程度のスコアになった。

マスの価値

基本的には設定の通り、マスを覆う連結成分のサイズ×野菜の価値がそのマスの価値と考えるとよさそう。まだ出現していない野菜については時刻が離れると価値が指数的に下がるとして調整した。時刻の値は野菜の出現日と消失日の2種類があるが、消失日に従って下がるとしたほうがよかった。

また、既に出現している野菜についても、やはり消失日が遠いと価値が指数的に下がるとしたほうがスコアがよいようだった。

マスの価値の伝搬

現在か近い未来に価値の高い野菜が生えるマスの周辺は価値が高いと考えられる。ただ、具体的に価値をどう伝搬するかが問題だった。周辺にどれだけ野菜が多かろうと1ターンで覆えるマスは1つだけなので、野菜が多いエリアを過大評価しないようにする必要がある。

いろいろ試した結果、最大連結成分からの最短経路DAGを作って、その逆順に各頂点$v$に$\max_{pはvの親頂点}(pの価値)$に減衰率を掛けたものを加算していくことにした。

• これだと距離について指数的に価値が減っていくことになるけれど、価値が3倍なら3ターン掛けてでもいくべき、と考えると反比例で減っていくほうが自然に思える。ただ、こちらは高速な表現ができなかった。
• 最大連結成分から到達する前に消失してしまう野菜の価値は伝搬しないようにする。

連結していることの価値

収穫機の連結性は維持したい。これを収穫機のないマスについて言い換えると、連結成分の隣は価値が大きい。収穫機のあるマスについて言い換えると、連結成分の関節点は非関節点より価値が大きい。

収穫機が数個のうちはいくつかの連結成分に分離して遠くの野菜を取りに行く可能性も考慮するつもりだったが、試してみるとそれで得られる利益がほぼないことがわかったので、最終的にはひとつの連結成分を伸縮することを前提とした方針に変えた。つまり、評価関数に含めるのではなく、収穫機を撤去するマスは非関節点で、収穫機を置くマスは連結成分の隣とした。

また、下記のビームサーチをする際には収穫機のあるマスの価値の総和を盤面の価値としたが、この時は非関節点が多い配置のほうが（次の撤去候補が多いぶん）やや良いという考えに基づいて、非関節点の評価値に1より少し大きい定数を掛けた。

ビームサーチ

上の評価関数を調整すると、局所的には明らかな問題が見つからなくなった。大きな改善があるとしたら「この日は上のほうに収穫機が集まっているけれど、長期的には実は下に集まったほうが得だった」のような状況をできるだけ減らすくらいで、これは適切に状態をまとめてビームサーチすることで実現できそうと思った。

ビームサーチの前提として似た盤面をまとめるために、全体を8×8の4個の領域に区切って、各領域に収穫機が何個あるかで盤面を同一視することにした。ただ、序盤についてはこの同一視はやりすぎで、区切る領域を少し増やしたほうが良いようだった。最終的には時間経過で16個→5個→4個と分割数を減らすように調整した。

終盤のほうが重要なのでビーム幅は終盤に大きいほうがよく、幅30から幅150まで増えていくようにした。

まだ収穫機を買うのをいつ止めるかという問題が残っている。今度は収穫機の調達数で全探索するわけにもいかないので、830日目以降は買わないという単純な仕組みにした。ここは時間があればもう少し詰めたかった。

ARC 126 E - Snack

• 問題
• AC

子供$i$が種類$j$の菓子を$x_{i, j}$個もらうとすると、与えられた問題は以下の条件で$\sum x_{i, j}$を最大化する問題と考えられる:

1. $\sum_{j=1}^Nx_{i,j} \le C_i \qquad\forall i \in [M]$
2. $\sum_{i=1}^Mx_{i, j} \le A_j \qquad \forall j \in [N]$
3. $0 \le x_{i, j} \le B_i \qquad \forall i \in [M], \forall j \in [N]$
4. $x_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$

ただし、$[M] = \{1, 2, ..., M\}, [N] = \{1, 2, ..., N\}$。実は4の整数制約は外してもよい。つまり、このILPの最適解はLP緩和の最適解にもなっている。以下はConfortiのInteger Programmingのp. 133を基にした説明。

---

定義: $m \times n$行列$A$の行を2つの集合$S$と$R$に分割する: $S \dot{\cup} R = [m]$。$S$の行ベクトルの総和 - $R$の行ベクトルの総和が$0, \pm 1$のみからなるベクトルであるとき、$S, R$を$A$の公平な行二彩色 (equitable row-bicoloring) と呼ぶ。

定理: 行列$A$が$0, \pm 1$のみからなり、各列の非ゼロ成分は高々2個であるとする。$A$が公平な行二彩色可能であれば、全ユニモジュラである。

上の制約の1, 2の係数行列について考えると、定理の条件を満たす（1の行と2の行に分割すれば公平になっている）ので全ユニモジュラである。

定理: $A$を$m \times n$整数行列とする。$A$が全ユニモジュラならば、任意の$l, u \in \mathbb Z^n, d \in \mathbb Z^m$について凸多面体$Q := \{x: Ax \le d, l \le x \le u\}$は整数多面体である、

この定理より上の制約1～3によって与えられる凸多面体は整数多面体なので、任意の目的関数について、（有界なら）最適解の少なくとも一つは整数解である。

---

従って、ILPに関しても強双対性が成り立つので、上のILPの最大値はLP双対の最小値に等しい。双対問題は以下の条件で$\sum_{i=1}^MC_ip_i + \sum_{j=1}^NA_jq_j+\sum_{i=1}^MB_i\sum_{j=1}^Nr_{i, j}$を最小化する問題である:

• $p_i + q_j + r_{i, j} \ge 1 \qquad \forall i \in [M], \forall j \in [N]$
• $p_i \ge 0, q_j \ge 0, r_{i, j} \ge 0 \qquad \forall i \in [M], \forall j \in [N]$
• $p_i, q_j, r_{i, j} \in \mathbb Z \qquad \forall i \in [M], \forall j \in [N]$

双対問題を、$M \times N$のグリッドのいくつかの行と列を選択して覆うようなイメージで解釈した:

• 行と列の集合$S \subseteq [M], T \subseteq [N]$を任意に選ぶ。（$p_i=1$であるような$i$と$q_j=1$であるような$j$を選ぶ）
• $i \in S$についてコスト$C_i$を払う。
• $j \in T$についてコスト$A_j$を払う。
• $S$に含まれる行と$T$に含まれる列に覆われないすべてのマス$(i, j)$についてコスト$B_i$を払う。

最後の「覆われない」の部分の扱いが面倒に見えるので、さらに言い換える:

• 最初にコスト$N\sum_{i=1}^MB_i$を払っておく。
• $S \subseteq [M], T \subseteq [N]$を任意に選ぶ。$k=|T|$とする。
• $i \in S$についてコスト$C_i-(N-k)B_i$を払う。
• $j \in T$についてコスト$A_j-\sum_{i=1}^M B_i$を払う。

さて、$[N]$から$k$点選ぶと決めたときの最小コストについて考える。$S \in [M], T \in [N]$について$(N-k)\sum_{i=1}^MB_i + \sum_{i \in S}(C_i-(N-k)B_i)+\sum_{j \in T}A_j$が総コストである。$T$は$A_j$の小さいほうから$k$個取ればよく、$S$のほうは$C_i-(N-k)B_i < 0$であるものだけ取ればよい。$C_i-(N-k)B_i$は$k$が減少すると一点で正から負に切り替わる。具体的には$k \le \lfloor (NB_i-C_i)/B_i \rfloor$で0以下になる。したがって、この閾値を超えた$i$について$C_i$と$B_i$の総和を保持することにすれば$k$ごとに${O}(1)$で計算できる。$(A_i)$のソートが必要だから全体の計算量は${O}(N \log N + M)$。

---

LPの整数性について追記した。

日本橋ハーフマラソン 2021

• 提出

A - 魔法使いXの戦い

308662点。1つのモンスターにつき、だいたい3回くらいパワーアップできる計算で、3回ならひとつずつ最適な組み合わせを貪欲に取っていけそう。素朴にやると${O}(N^4)$だが、最後は二分探索でよいので${O}(N^3 \log N)$。

まだ回数に余裕があるので、末尾に近いモンスターは4回パワーアップしたいが、これは素朴に探索すると間に合わない。$q$に選ぶモンスターから近い数値で固まっているものを省いたりして間に合う程度のノード数に減らした。

探索する順番を工夫すれば少し伸びるかもと思っていろいろ試したが伸びず。

B - マッサージチェア2021

210901点。一点のパワーを変更して干渉する点のパワーを減らすだけの山登りをした。すぐに収束してしまうが、簡単に書けそうな他の遷移もないので多点スタートなどで時間を使い切ることにした。一点のパワーを下がるほうに変更するような完全に無駄な遷移も入れてしまっているなど、いろいろ詰めが甘かった。

AtCoder Adのように、1つのノードを大きくして周りのノードを小さくする操作と、1つのノードを小さくして周りを大きくするような操作を組み合わせて再帰的に頑張るともう少しよくなるかもと思ったが、この時間では書ける気がしなかった。

マス$(i, j)$のパワーを表す変数を$p_{i,j}$とし、マス$(i, j)$に正のパワーを与えることをバイナリ変数$x_{i, j}$で表すと、素朴なMIP定式化は

maximize $E_{i, j}p_{i, j}$
subject to

• $0 \le p_{i, j} \le Nx_{i, j}$
• $p_{i_1, j_1}-N(1-x_{i_2, j_2})\le |i_1-i_2|+|j_1-j_2|-1$

という感じか。

---

解説を見ると全然問題の性質をとらえられていないなと思う。短時間コンテストは自明な方針を手早く実装したあと細部の詰めで同方針の人にちょっと勝つだけでそれなりの順位がとれてしまうことがありそう。

Treapのunionの計算量に関するメモ

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf に$m, n \ (m \le n)$要素のTreapのunionで期待計算量が${O}(m \log (n/m))$であるものが紹介されている。これを使うと次のことができる:

1要素のTreapが$N$個与えられたとし、これらのTreapに任意の順番で$N-1$回unionを適用して$N$要素のTreapを作るとする。この時、全体の期待計算量は${O}(N \log N)$である。

これはマージテクと同じように理解できる:

まず、定数$B$が存在して$m, n\ (m \le n)$要素のTreapのunionの期待計算量は$B m \log (n/m)$以下である。

求める計算量を$T(N)$とする。$C>0$が存在して$N$未満の整数$x$については$T(x) \le C x \log x$が成り立っていると仮定する。このとき、$T(N) \le C N\log N$であることを示せばよい。この際、$C \ge B$としてよい。

$$ T(N) \le \max_{m+n = N} \bigl (Bm \log \frac{n}{m}+ T(m) + T(n) \bigr) $$

であるから、任意の分割$N = m+n \ (0 < m \le n)$について$Bm \log (n/m) + T(m) + T(n) \le C N \log N$が成り立つことを示せばよい。実際、次のように示せる:

$$ \begin{aligned}& Bm \log \frac{n}{m}+ T(m) + T(n) \\ \le \ & B m \log \frac{n}{m} + Cm\log m + C n \log n \\ \le \ & C \bigl (m\log\frac{n}{m} + m\log m + n \log n \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n \log \frac{n}{m}m \bigr ) \\ = \ & C \bigl (m \log \frac{n}{m} + m\log m + n\log \frac{n}{m} + n \log m \bigr ) \\ = \ & C \bigl ((m+n) \log \frac{n}{m} + (m+n)\log m \bigr ) \\ = \ & C \bigl (N\log \frac{n}{m} + N \log m \bigr) \\ = \ & C(N\log n - N\log m+ N \log m) \\ = \ & CN\log n \\ \le \ & CN\log N \\ \end{aligned} $$

（$\log 1 = 0$ 問題があるのであまり正確でない。）

JAG Summer Camp 2017 Day 1 C - すごろく

• 問題
• AC

まずは$B_i$がすべて$0$であるような問題を考える。ループがない、つまり同じマスに二回止まることがないので、ゴール以前の各マスに止まる確率を足し合わせたものが求める期待値になっている。

$p(i) =$ サイコロを振って$i$が書かれた面が出る確率 $\operatorname{dp}[x] =$マス$x$に止まる確率

とするとき、0-basedで考えると遷移は

$\operatorname{dp}[x] = \sum_{0 \le k \le x}\operatorname{dp}[x-k]p(k)$

となって、これはオンラインFFTで解ける形になっている。

$B_i$が必ずしも0でない場合について考える。$B_x > 0$であるようなマス$x$については、オンラインFFT中に$\operatorname{dp}[x]$に加算する時に、代わりに$\operatorname{dp}[x+B_x]$に加算すればよい。また、$B_x < 0$、つまり休みのマスについては、そのようなマスに止まる確率$\times |B_x|$を結果に足せばよさそう……だが、他のマスから$B$の影響で進んできた場合は休まないので、$\operatorname{dp}$を構成し終えてから$\operatorname{dp}[x] \times |B_x|$を後で足すと正しく計算できない。やはりオンラインFFT中に$\operatorname{dp}[x]$に加算する瞬間に結果に足す必要がある。

KUPC 2016 H - 壁壁壁壁壁壁壁

• 問題
• AC (slope trick)
• 部分点 (単体法)

位置$i$から$i+1$に補強材を移動する量を$x_i$として制約を書き下す。$n=4$なら

• $A_1-x_1 \ge B_1$
• $A_2 + x_1-x_2 \ge B_2$
• $A_3 + x_2-x_3 \ge B_3$
• $A_4+x_3 \ge B_4$

という制約の下で$|x_1|+|x_2|+|x_3|+|x_4|$を最小化する問題になっている。

$f_i(x)$を$x_1, ..., x_{i-1}, x_i=x$までを決定した際の最小コストとする。slope trick向けに制約を変形すると、

• $x_1 \le A_1-B_1$
• $x_1 \ge x_2-(A_2-B_2)$
• $x_2 \ge x_3-(A_3-B_3)$
• $x_3 \ge B_4-A_4$

となって、一番上の$x_1$に関する制約を無視すると$f_i$の漸化式が得られる:

• $f_1(x) = |x|$
• $f_2(x) = \min_{t \ge x - (A_2-B_2)}f_1(t) + |x|$
• $f_3(x) = \min_{t \ge x - (A_3-B_3)}f_2(t) + |x|$

登場する操作はすべてslope trickで表現できて、答えは凸性により、$B_4-A_4$か$\argmin_xf_3(x)$の大きいほうの位置で$f_3$の値を求めると得られる。

制約$x_1 \le A_1-B_1$については、この範囲を超えると高いコストがかかることにして対処したい。$x_1$が$A_1-B_1$を$1$超過することによる利益が高々$C$であるとき、$f_1(x) = |x| + C\max(0, x-(A_1-B_1))$とすればよい。$C$の具体的な値としては、制約を$1$だけ破っている状態を解消するために1つの補強材を端から端へ移動すると$N-1$のコストがかかるので、$N-1$でよい。

CodeChef - CCDSAP Exam

• 問題
• AC

slope trickの練習問題として解いた。

人$i$の初期位置を$a_i$とし、人$i$を位置$x$に配置した場合の人$1, 2, ..., i$に関するコストの総和の最小値を$f_i(x)$とする。

左右の境界を無視すると$f_{i}(x) = \min_{t \le x-2}f_{i-1}(t) + |x-a_{i}| = \min_{t \le x}f_{i-1}(t-2)+|x-a_i|$と表せる。これだけなら普通のslope trickで解けるが実際には境界を越えられないところが難しい。

境界を越えたら大きなコストがかかるように、$|x-a_i|$の代わりに定数$C$を定めて$C\max(0, 1-x) + |x-a_i| + C\max(0, x-N)$を追加することを考えたが、これは優先度付きキューに一つずつ挿入していく方法では難しそう。平衡二分木で多重集合を管理すればいけそう？ → 平衡二分木slope trickを作ろうとしたが、最小値の更新が自明にはできない。おそらく任意の$x$について$f(x)$の値が取得できる必要があって、実現方法がわからなかった。ただ、$\min$がわからなくても$\argmin$は容易に取得・更新できる。これだけわかれば最適解を貪欲に復元できそう。最適解における人$i$の位置を$y_i$とする。$y_N=\argmin_x f_{N}(x)$は既知であり、$y_{i+1}$が既知であるとき$y_i$は

$$y_i = \min(\argmin_x f_{i}(x), y_{i+1}-2)$$

と決定できる。$\argmin$が複数ある時はどれを取ってもよい。