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に関する双対、つまり元の問題のLP緩和の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$が複数ある時はどれを取ってもよい。

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

• 問題
• 提出

辛うじて全完したが、最後の問題の正しい解法がわからなかった。

K - 急ぎ旅

最短経路DAGを作ってからDPした。

ダイクストラと同時にできるらしい。確かに。

L - たくさんの最小値

最小値の列挙は遅延セグメント木上を二分探索すればできる。いつもこの方針でやっていて、想定解のようにノードに持たせる情報を増やすやり方でやったことがない。後者でないと難しい設問ってあるんだろうか。

M - 分割

明らかに最小費用流だと思ったが、グラフの作り方で長時間かけてしまった。

辺の下限流量を決めて変形するイメージで作った。まず、整数$A_i$を表す各位置$i$を$i_{\mathrm{in}}, i_{\mathrm{out}}$に分割する。

• $S$から$i_{\mathrm{out}}$に容量1、コスト0の辺を張る
• $i_{\mathrm{in}}$から$T$に容量1、コスト0の辺を張る
• $i_{\mathrm{out}}$から$T$に容量1、コスト$C$の辺を張る
• $i < j$であるすべての$j$について、$i_{\mathrm{out}}$から$j_{\mathrm{in}}$に容量1、コスト$|A_i-A_j|$の辺を張る

想定解は「通ってほしい辺」のコストを$-\infty$にしてから変形する考え方のようだった。こちらは全然考えたことがなかった。

N - モノクロデザイン

JOI 2012 春合宿 - fortune_telling

O - コンピュータ

$(B_i)$が狭義単調増加の場合が解ければよい。また、世界には$B_1, ..., B_N$円のコンピュータしか存在しないとしてよい。

$\operatorname{dp}[x] = x$日目でちょうどコンピュータを買い替えなければならない場合の最大所持金額

とする。$x$日目に買えるコンピュータは、所持金以下であるような最大価格のコンピュータを$r$として$B_x, B_{x+1},..., B_r$のいずれかであり、$B_y$を買うとすると遷移は$\operatorname{dp}[y+1] := \max(\operatorname{dp}[y+1],\operatorname{dp}[x]+A_{x+1}+A_{x+2}+...+A_{y+1}-B_y)$。$A_{x+1}+A_{x+2}+...+A_{y+1}$の部分を累積和で計算すると、このDPは${O}(N^2)$である。

$o(N^2)$にする方法がわからなかった。試しに、買うコンピュータを$x$か$r$だけにしたものを投げると半分以上は通る。それならと思って両端から2000個程度（$x, x+1, ..., x+2000$と$k-2000, ..., k-1, k$）の遷移に限定してみたらACした。

解説を見た。

$\operatorname{dp}[x] =$ コンピュータ$x$を買った時点での支出の最小値

とする。コンピュータ$p$を買ってから次に買うコンピュータとして$x$を選べる必要十分条件は$A_1+...+A_{p+1}-\operatorname{dp}[p] \ge B_x$であること。これが成り立つような$p$について、$\operatorname{dp}[x] := \min_p\operatorname{dp}[p] + B_x$と更新すればよい。

実装としては、range minを載せた平衡二分木のキー$A_1+...+A_{p+1}-\operatorname{dp}[p]$に値$\operatorname{dp}[p]$を対応させておけば、キーが$B_x$以上のノードについての$\operatorname{dp}[p]$の最小値を高速に求められる。

---

Oは今までのPASTで一番難しく感じた。

CodeChef - Short in Average

• 問題
• AC

$A$から$B$へのウォークが与えられたとする。このウォークが閉路を含んでいて閉路の平均長がウォークの平均長より小さいなら、何回も回ればウォークの平均長を閉路の平均長まで下げられるし、そうでないなら閉路を除いて損しない。また、閉路を含まないウォークは高々$N-1$本の辺しか含まない。従って、以下のようなアルゴリズムが考えられる:

1. $B$に到達できる頂点の集合$W \subseteq V$を求めて、以降は$W$による誘導部分グラフ上で考える。
   • この時点で$A$と$B$がつながっていなければ終わり。
2. Bellman-Ford法のようなDPをして、高々$N-1$辺を通るという条件の下での$A$から$B$までの最短平均長ウォークの長さを求める。
3. $A$から到達できる最短平均長閉路の長さを求める。
4. 2と3の小さいほうを取る。

実装上は3のアルゴリズムが2のDPを含んでいる。2は$N-1$回、3は$N$回回す必要があるので、最初から$N$回回せばよい。

3については、$\operatorname{dp}[k][v] =$ちょうど$k$本の辺を使う場合の$S$から$v$への最短経路、として

$$ L = \min_{v \in N}\max_{k = 0, ..., N-1} \frac{\operatorname{dp}[N][v] - \operatorname{dp}[k][v]}{N-k} $$

が求める長さである。ただし、$S$から到達できない頂点がある時にそのまま扱うと$\infty - \infty$という計算が起きてしまうので、$\operatorname{dp}[N][v] = \infty$の場合は除いて計算する。全部そう（＝$N$回目で到達できる頂点がない）なら閉路がないグラフなので$L = \infty$になるべきで、つじつまがあっている。

解説は「平均長が$L$以下のウォークが存在するか？」という判定問題を解いて二分探索する方針だった。判定問題は、すべての辺の重みから$L$を引いた時に$S$から$T$への長さ$0$以下のウォークが存在するかどうかで判定できて、これはやはりBellman-Fordで調べられる。

CODE FESTIVAL 2016 Grand Final D - Dice Game

• 問題
• AC

Petrの純粋戦略は$2$通り:

• 赤を選ぶ
• 青を選ぶ

touristの純粋戦略は$2^6=64$通り:

• どの目が出ても赤と答える。
• 2, 3, ..., 6が出たら赤と答え、1が出たら青と答える。
  ...
• どの目が出ても青と答える。

これらの混合戦略の中からお互いに最適戦略を取った時にtouristが勝つ確率を知りたい。

$a_{ij} =$ Petrが戦略$i$を取ってtouristが戦略$j$を取った時にtouristが勝つ確率、とすると行列$(a_{ij})$の見た目は

$$ \begin{bmatrix} 1 & 1-p_1 & 1-p_2 & 1-(p_1+p_2) & ... & 0 \\ 0 & q_1 & q_2 & q_1+q_2 & ... &1 \end{bmatrix}$$

となっている。touristの混合戦略を$(x_1, ..., x_{64})$で表すとき、touristは$a_{1, 1}x_1 + ... + a_{1, 64}x_{64}$と$a_{2, 1}x_1 + ... + a_{2, 64}x_{64}$の小さいほうを最大化したい。この問題は以下のLPになっている:

• $\textrm{maximize} \ z$
• $a_{1, 1}x_1 + ... + a_{1, 64}x_{64} \ge z$
• $a_{2, 1}x_1 + ... + a_{2, 64}x_{64} \ge z$
• $x_1+ ... + x_{64} = 1$
• $x_1, ... x_{64} \ge 0$

これは単体法などで解けるが、もう少し簡略化する。touristの戦略は「目$i$が出たら$y_i$の確率で赤を選ぶ」という形で表せる。Petrが赤、青を選んだ時にtouristが勝つ確率はそれぞれ$p_1y_1+...+p_6y_6$、$q_1(1-y_1)+...+q_6(1-y_6)$であり、touristはこれらの小さいほうを最大化したい。この問題は以下のように書ける。

• $\textrm{maximize} \ z$
• $p_1y_1+...+p_6y_6 \ge z$
• $q_1(1-y_1)+...+q_6(1-y_6) \ge z$
• $y_1, ..., y_6 \in [0, 1]$

これもLPだけれど、変数が少ないので非基底変数の組み合わせを総当たりするだけでもよさそう。

AHC 004 A - Alien's Genome Assembly

• 問題
• AC

$s_i$を盤面のどこかに上書きする遷移だけの焼きなましをした。

• 遷移の際のスコア更新について。変更に関わるそれぞれの行・列を（折り返しを考慮して）31文字の文字列とみなして、Aho-Corasickで$(s_i)$全体とマッチングした。マッチング結果は行・列ごとに長さ$M$のビット列に保持して、最後にすべてのビット列のORを取って立っているビットを数えた。
  • 最初は$(s_i)$中の同一文字列をまとめて1つ1つに重みを与えていたが、重み付きになると最後の「立っているビットを数える」部分でワードサイズ高速化ができなくなって逆に遅くなった。
• 縦に書く文字列と横に書く文字列を混在させようとするより、どちらかに絞ったほうがだいぶ得点効率がいいことに気づいたので、横に書くだけにした。
• 行にだけ文字列を書くとした上で、変更に関わるすべての列を遷移ごとにマッチすると、特に$(s_i)$の平均長が大きい場合に調べるべき列が多くなって重くなる。結果を見ていると、平均長が大きい入力は縦にマッチするパターンがほとんどないようなので、列に関するマッチを完全に無視することにした。具体的には6以上なら列は無視して、5以下は列のマッチも調べた。
  • 焼きなましの遷移回数は、前者が$2 \times 10^6$、後者が$4 \times 10^5$くらいだった。
• 盤面に存在しない$s_i$から乱択する遷移と$(s_i)$全体から乱択する遷移を入れていたが、前者がうまく高速化できずにボトルネックになっていたので、全体から乱択するだけにした。
  • 追記: もっと単純に、盤面に存在する$s_i$を引いたら何回かサンプルしなおす、でよかった。改善は+0.2%程度。
• 平均長が大きい入力は3秒使いきる前にどこかの山に収束してしまうようだったので、平均長が8以上の入力については多点スタートした。

振り返り

• prefixとsuffixが重なる2つの文字列を1つにすることで点を伸ばしている人が多数いるようだ。これは最初に考えたのだけど、具体的にどの文字とどの文字を連結するべきかを考える必要があるし、焼きなましと相反しないだろうと思って後回しにした結果、最後まで放置してしまった。雑な貪欲でもいいから試してみるべきだったな。

AHC 003 A - Shortest Path Queries

• 問題
• AC

最小二乗法による$H, V$の推定をベースにいろいろやった。辛うじて97%に達した。

M=1

とりあえず、$M=1$のケースしか来ないとして$H, V$を推定することを考える。報告されたパスの長さを$W$として、パスが行$i$を$r_i$回、列$j$を$c_j$回通るとする。このとき、$\sum_{i: 行}r_iH_i + \sum_{j: 列}c_jV_j$と$W$が近くなるように$(H_i), (V_j)$を選びたくて、これは最小二乗法(OLS)が使えそう。得点は正規化されているので$W$で割って、

$$ \Bigl (\frac{1}{W} \bigl(\sum_{i: 行}r(i)H_i + \sum_{j: 列}c(j)V_j \bigr) - 1 \Bigr)^2 $$

の総和を最小化することを目指す。OLSはクエリ数を$Q$、変数の数を$d$として${O}(Qd^2)$でできる。

• パスの重みなし長さ$l$が大きいと、$\delta, \gamma$の平均の分散（≒誤差の分散）が小さくなっていくはずなので、パスごとの誤差の分散を揃えるために重み付き（式に$\sqrt l$を掛ける）にしてみた。直接のスコアにはほぼ影響しなかったけれど、後述の$M$の判定にかなりよい影響があったので残した。（ただ、そうなる理由がよくわからない。）
• 特にクエリが少ないうちは多重共線性の問題があるので、OLSの行列の対角成分に微小な定数を足して正則にするやつ（リッジ回帰と呼ばれているもの）をした。
• 毎回OLSすると遅すぎるし、クエリが一定数を超えるとだいたい収束しているようだったので、クエリを150個処理するまでは毎回OLSし、それ以降は25回に1回にした。
• OLSは素朴な掃き出し法でやった。疎行列なのでもっと速い方法はあるらしいけれど、後半のOLSの頻度を上げてもほとんど得点に結びつかなかったので、コンテスト中は無視していた。

M=2

$M=2$の場合、$H, V$の値が行、列ごとに2種類あり、境界がわからないのでその推定もする必要がある。境界を決めつければ上と同様のやり方で$H, V$が推定できるので、その際のRMSEをスコアとして境界を探索する焼きなましは考えられる。ただ、素朴にやると1回のOLSが重すぎるという問題がある。そこで、ある一行$i$の境界を移動させたときのRMSEを最小化する問題を局所化して、$H_{i, 0}, H_{i, 1}$だけを推定する二変数の回帰と考えることにする。このOLSは${O}(クエリ数)$でできるので、焼きなましの遷移としては十分に速い。

• 最初のうちは多項式回帰や3分割、4分割のOLSも試したが、普通にやると収束が遅すぎてうまく扱えなかった。

Mの分類

$M$は与えられていないので推定する必要がある。クエリを150回処理するまでは$M=1$を想定したOLSをして、その時点でのRMSEを見て一定より大きければ$M=2$、とするだけで96%程度の正解率があるようだった。ほかにも相関のある指標はいくつかあったけれど、正解率100%でも総スコアに大きな影響はなかったので追求しなかった。^[1]

• もう少し精密に、10回目、20回目、30回目、...で$M=2$である確率が（例えば）98%以上になったら$M=2$の処理に移行する、みたいな考え方もありそうだったが、そもそも移行を早めても得点が上がらない（$M=2$の入力に対しても、最初はむしろ$M=1$向けのモデルを適用したほうが効率がよい）ようだった。

OLS以降

クエリ数が増えると、個別の辺の重みもある程度は推定できそうと思った。推定した$(H_i), (V_j)$をベースに、RMSEをスコアとして各辺の重みを変更する山登りをすると、$M=1, 2$ともに点が伸びた。

• 焼きなましで点が伸びなかったので、速度を重視して山登りにした。
• 素朴にやるとオーバーフィットするので、正則化（各辺の重みの$H, V$との差についてのRMSEも山登りのスコアに足す）を加えたりしたが、十分にコントロールできている気がしない。
• 通った回数の多い辺上位200個くらいを選んでOLS、も試したが山登りを超えられなかった。

振り返り

• 統計の知識がなさすぎるので、問題を見たときにけっこう困った。ただ、最初の印象に反して、素朴な回帰と局所探索を調整しているだけでまあまあスコアが伸びていった。
• Woodburyの恒等式でOLSの差分更新ができるらしい。確かにこういうものを探していた。
• 通った回数の少ない辺や行・列を少しだけ楽観的に評価したり、（使う行・列は少ないほうが質の高い情報が得られるので）最初のうちは方向転換にペナルティをつけたりするという工夫で点を伸ばしている人がかなりいるようだった。どの情報を得るかという観点を後半になって忘れてしまったのは反省点。
  • 前半のことを思い出すと、通ったことのない行・列を優先して通るようにすると多重共線性の問題が大きくなってむしろスコアが下がってしまうので捨てて、それ以降ほとんど考えなかったんだよな。

---

1. 0.03%程度の上昇は見込めたので影響が皆無なわけではなかったが、この辺の知識がなさすぎて後回しにした結果、結局やらなかった。 ↩︎

AHC 002 A - Walking on Tiles

• 問題
• AC

とりあえず愚直ビームサーチを書いてみると盤面全体を移動できないうちに行き詰まってしまうことがわかる。

こういうのをどうするかという時に手札があまりなくて困るが、安直な対処として、全体を10x10マスの25個のブロックに区切ってブロックを頂点とするグラフでハミルトンパスをひとつ与えて（偶奇によってはハミルトンパスがなくて24ブロックしか渡れないが）それに沿うような経路を探索するというのはありそう。ベスト方針とは思えないので少しためらっていろいろ考えたが、他に大した案を思いつかないので実装した。

現在のブロックを$B_1$、次のブロックを$B_2$とするとき、$B_1$内では幅6000のビームサーチをする。移動先は$B_1$内のいずれかのマスか、$B_2$のマスで$B_1$に隣接しているもの（高々10個）に限る。後者は最高点の経路だけ保持する。$B_1$のビームサーチが終わったら$B_2$のマスで$B_1$に隣接しているものを始点に$B_2$のビームサーチを始める。これで$5.2 \times 10^6$点程度だった。もう少し考えると、$B_1$と$B_2$にまたがるタイルを取る/取らないで$B_2$における探索に影響があるので、それらの違いも考慮して経路を保持する（高々$10 \times 2^{10}$状態だが、平均的にはそれよりだいぶ小さい。) これで$5.3 \times 10^6$台に上がった。ビームサーチの幅を増やすと点はある程度上がるようだったので、最後の数十分は高速化をして幅8000のビームサーチが間に合うようにしたが、更新できなかった。

---

• 結果を見ると、2個程度のテストケースで25個のブロックを渡りきる前に行き詰まって終了しているようだ。そうなる可能性は認識していたけれど、seed=0から99まででは大丈夫だったので軽視していた。応急処置としては、時間があまりすぎていたらもう一回別のハミルトンパスで探索する等は思いつくが……
  • コンテストが終わったあとで調べていたが、そもそもどう動いても隣接ブロックに移れないか、移れる経路が極端に限られるような配置がたまにあるようだ。
• 最初の考察で、タイル毎に取るほうを決め打つと普通の最長経路問題になるなと思ってしばらく考えていたが、それを利用する方針は思いつかず。
• 経路を一部破壊してからつなぎなおす方針で上位に入っている人がけっこういるようだ。これも考えたけれど、4時間で詰められると思えなかったので捨ててしまった。

ABC 199 E - Permutation

• 問題

$\operatorname{dp}[S] :=$集合$S$に含まれる整数を数列の先頭$|S|$箇所に（制約を満たすように）配置する場合の数、としてDPできる。$S$に整数$t$を追加して$S \cup \{t\}$に遷移する時、制約は$X_i=|S|+1$であるようなものだけ調べればよい。

また、状態を入れ換えて$\operatorname{dp}[S] :=$集合$S$に含まれる位置に整数$1, 2, ..., |S|$を配置する場合の数、としてもDPできる。この場合は$|S|$に位置$t$を追加して$S \cup \{t\}$に遷移する時、制約は$Y_i = |S|+1$であるようなものだけ調べればよい。

前者と後者は同じ形の遷移になっていて、一方を書いて入力の$X$と$Y$の順番を「間違える」ともう一方になって同じ答えがでる。これらの数えているものは、数列を置換とみなしたときに逆置換で一対一対応している。

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

• 提出

リアルタイム受験した。O以外を通して94点だった。今回は前半の複数の問題にはまってしまって、辛うじてエキスパートという結果だった。

G - 一日一歩

素直に考えると最短経路問題を解けばよくて、通りたい道の直近で通れる日はRMQ上の二分探索で突き止められるが、Gでそんなことする必要がある？ と悩んで時間を消費した。結局、最初に考えた通りに実装した。

H - カンカンマート

$T$の値によって2列にわけてどちらも昇順ソートして、$T=0$をできるだけ取るような構成にしてから$T=1$をひとつひとつ増やしていけばよい……のだが、それが見えずに三分探索などをして時間をかなり消費した。

L - 都市計画

道路の端点がタワーか環状交差点上になければならないという条件を見落としていて、解ける問題に見えなくて困っていた。

M - 等しい数

似た問題をCodeChefで解いたことがあったにも関わらず、長時間はまった。CodeChefの問題は平方分割で解いたのだが、実装が大変だった記憶があるし、この問題のほうがハッシュテーブルへのアクセスが多くなりそうだし、制約も厳しいし、ということで平衡二分木で解くことにした……のだが、複数箇所でバグらせてしまった。

区間を平衡二分木で管理するやつを改造して使うことにして、手持ちのものはmapではない（区間に対応する値がない）ので、区間$[l, r)$に入っている値は別に用意した配列の位置$l$に保持することにしたのだが、それが間違いだったかもしれない。区間の分割・消去・挿入などの操作間で、区間に入っている値を正しく保つための処理が複雑になってしまって、手におえなくなるところだった。

N - 活動

順番を固定できればラッキーと思って調べると、$a_i/b_i$の降順でソートしてよいことがわかるのでソートしてDPする。（しかし、最後の活動の取り方を素朴なDPで正しく扱えているのか自信がなかった。）

O - 最短距離クエリ

先に開いて少し考えたがわからなかった。似た設定の問題としてUTPC 2011 - 巡回セールスマン問題があったのを思い出したが、そもそもこれも解けていなかった。

ABC 198 F - Cube

• 問題
• AC

サイコロが手元にあったので、回しながら考えた。まずはバーンサイドの補題を思い出す:

• 群$G$が集合$X$に作用するとする。この時、作用に関する同値類の総数は次の数に等しい:

$$\frac{1}{|G|}\sum _{g\in G}|F_g|$$

• ただし、$F_g$は$g$のfix、つまり$F_g=\{x\in X|g(x)=x\}$。

したがって、正六面体に対する回転操作で回転前と回転後が重なるものを列挙して、各回転に関するfixの大きさを求めればよい。正六面体に対する回転を分類すると以下の通り:

• $\mathrm{id}$: 恒等変換、つまり何もしない。1通り。
• $\alpha$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$90\mathrm{°}$回転する。どちら向きに回転するか述べていないが、ベクトルとみなして反時計回りに回転するとすると、$AB$と$BA$で別の回転になって$3\times 2=6$通りある。
• ${\alpha }^2$: ある面の中心$A$と向かいにある面の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。3通り。
• $\beta$: ある辺の中心$A$と向かいにある辺の中心$B$を結ぶ直線を軸に$180\mathrm{°}$回転する。辺対が6ペアあるので6通り。
• $\gamma$: ある頂点$A$と向かいにある頂点$B$を結ぶ直線を軸に$120\mathrm{°}$回転する。頂点対が$4$ペアあって、やはり回転する方向が2通りあるので$4\times 2=8$通り。

合わせて24通りあるので、fixの大きさを求めて全部足して24で割ればよいことになる。上の回転によってどの面とどの面が重なるかを調べると、以下の数え上げをすればよいことがわかる:

• $\mathrm{id}$: $x_1+x_2+x_3+x_4+x_5+x_6=S$の正整数解の総数を求めることに等しい。
• $\alpha$: $x_1+x_2+4x_3=S$の正整数解の総数を求めることに等しい。
• ${\alpha }^2$: $x_1+x_2+2x_3+2x_4=S$の正整数解の総数を求めることに等しい。
• $\beta$: $2x_1+2x_2+2x_3=S$の正整数解の総数を求めることに等しい。
• $\gamma$: $3x_1+3x_2=S$の正整数解の総数を求めることに等しい。

$\mathrm{id},\beta ,\gamma$は単純な重複組み合わせに帰着するが、$\alpha ,{\alpha }^2$がやや面倒に見える。

たとえば$\alpha$に関しては$1/(1-z{)}^2(1-z^4)$の$z^{S-6}$の係数を求めることに等しく、$1/(1-z{)}^2=\sum (\genfrac{}{}{0ex}{}{i+1}{i})z^i$（負の二項定理）を利用して$1+z^4+z^8+...$と掛けたときにどうなるか考えればよい。（自分は計算をバグらせてWolframAlphaに頼った） → $x_3$を決め打つと$x_1+x_2=S-4x_3$の正整数解が$S-4x_3-1$個だから、$\sum _{x=1}(S-4x-1)$を非負の範囲で計算すればいいのか。難しく考えてしまった。

---

見て何をすればよいかはわかったが、WolframAlphaがなければコンテスト中にはACできていなかった。結局は計算力なんだよな。

$mod6$で多項式になりそうなのでラグランジュ補間、というのを見てなるほどと思った。とはいえ小さいケースをちゃんと求めるのにもある程度の考察は必要か。

https://q.c.titech.ac.jp/docs/progs/polynomial_division.html
そもそも母関数が書けた時点で貼るだけになるらしい。というか、これを知らなくても漸化式に直して行列累乗はできるのでそれは考えるべきだった。