確率分布の数列を $p$，答えの数列を $f$ とすると，

$\displaystyle{ \begin{aligned} f_0 &= 0 \\ f_i &= 1 + \sum_j p_jf_{i \oplus j} \qquad (i \neq 0) \end{aligned} }$

を解けば良い．

数列同士の bitwise XOR 畳み込み（$\ast$で表す）で書けるように $f_0$ の式の形を揃えたい．

$1 + \sum_j p_j f_j$ は状態 $0$ の平均再帰時間である．これは，マルコフ連鎖の性質から，$2 ^ N$ に等しい．

よって，数列 $g$ を $\displaystyle{ (1-2^ N,1,1,\ldots,1) }$ で定めると，

$\displaystyle{ f = g + p \ast f }$

となる．

数列 $e$ を $\displaystyle{ (1,0,\ldots,0) }$ で定めて，

$\displaystyle{ f=g \ast (e-p)^{-1} }$

を計算すればよい．

…と思って実装をすると，$0$ 除算発生！

よく考えると，$e-p$ をアダマール変換すると先頭の項が $0$ になってしまう（それ以外の項が $0$ になることはない）．

ところが，$f_0=0$ であることを既に知っているので $f$ をアダマール変換した結果の先頭の項はそれ以外の項の和の反数として求めることができる．めでたしめでたし．

提出

2020-11-07

ICPC 2020 国内予選参加記

振り返ると私とkort0nで今年の頭にもう1人のメンバーを探しているときは偉そうに「この瞬間の実力よりもモチベを重視しよう」などと言ってRubikunに声をかけたが、これは大正解で成長曲線の傾き的には今まさに抜かれようとしているあたりで、そうならないように頑張りたいところ。

なんやかんやで睡眠調整に失敗してかなり眠い状態で本番を迎えることになってしまい、普段は飲まない魔剤を買って臨む。

開始直後のページにアクセスできない焦りが収まってきたあたりでぬるっとコンテストが始まり再び焦る。

ABCは1問ずつ分担する方針だが自分は簡単目な問題にハマることが多く、低難易度埋めもしていて安定感のあるRubikunにBを任せて、Aをやることにしていた。どうでもいいがふざけてあらかじめ書いていたAの入力形式が当たっていた。

Bまでは普通に進んでいたがkort0nがCが解けないというかやたら実行時間がかかるというかで大変らしい。概要を聞くと高速素因数分解ライブラリで殴ればどうにかなりそうな気もするが解法もよくわかってないしパッと書ける気がしなかったので引き受けるのを渋る(カス)。結局引き受けることになってよくわからないままkort0nの言ってることをそのまま実装する。バグらせながらもしばらくして何とか通るが後から振り返るとかなり頭がついていなかった。

pの3乗根以下のpの約数xを全探索してxとp/xに分けた後、どちらをさらに分けるかの2通りを試してまた約数を列挙して…などとやっていたがxを3数の最小のものと思えばxをさらに分ける必要はないしpの素因数分解がわかっているのだから改めてp/xの素因数分解をする必要もない。

後ろの問題の解法が出てるわけでもなくただただCで詰まっているという最悪な時間帯が存在してかなりヤバい雰囲気が漂っていた。実際順位表を見たとき10位台後半でこのまま終わってしまうのか？と思った記憶がある。

直前に付け焼き刃の練習をして構文解析モチベが高まっていてDを考えるが非構文解析パートの解法が普通にわからない。が、Rubikunが冴えていてE、Dと立て続けに解法を出していてすごかった。

Dの実装が何故か重いと判断してまあ分割も明らかなので分担を提案して、Eをkort0n、Dを私とRubikunで全員実装しているという状態になってどちらも大体開始1時間後くらいのタイミングで通る。この辺りで安心はできないものの普通の空気に戻った気がする。

丁度FのACが出始めていて解くべきっぽい問題だと悟り全員で取り組む。考察を進めると最近冷えて悔しい思いをした問題に似ているので思い出しながらお絵描きをして共有をする。なんかこれがヒントになったらしくkort0nが解法を生やし、そのまま実装を任せることに。

結局木を作る前半パートと木上で問題を解く後半パートがあって、自分は前半パートの実装単体でも苦労したことがあったのでかなり大変そうだと思っていたのだが、結果的には想定よりかなり早く実装が終わっていて流石だった。どうやら自分が理解しきれてなかった後半パートがそこまで重くはなかったらしい。この間はサンプルを手で作ったり愚直解と突き合わせるためのケース生成コードなどを準備しながらGをなんとなく考えていた。

実装が大変な割にやたら通されていて簡単な解法があるのかと思っていたが愚直を書いて待つという手法が自分はすっかり頭から抜けていた。

ともかくFが通って通過を確信し緊張感が切れる。 GからLP双対系の波動を感じちょっと考えたりしていたがHの概要を聞き「流石に辺同士が接するとして良くて（良くないが…）あとは三分探索+最小包含円で良くね？」などと言い出し実装を始める。他人のライブラリをペタペタして実装するもサンプルの最後が合わなくて図示をお願いするとヤバいケースの存在が判明する。

エスパーにエスパーを重ねて実装を続けるも今度は計算時間が爆発して大変なことになっているうちにコンテストが終了した。

感想

とりあえずほっとしています3

2019-09-16

JAG夏合宿2019 参加記

たまには書こうという気持ちになった．

Day1

https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day1

この日（だけ）は本来のチームokimochiで参加．結果は8位でまあ冷えたほうだと思う．

ABC

1人1問担当で，自分はCをやったんですがペナこそ踏まなかったものの境界周りで散々バグらせた．今見たら00:56とかで本当に何をやってたんだ？

D

kort0nが初見でやばそうと言ってたけどなんか解いてくれて中華風Hardで整備したライブラリがあるので出来ますと言って書いた．

E

なんか最初みんな（？）見ててよくわからなかったけど重み付きUFでできるじゃんとなってやった． log取るのだとやばいねとかちゃんと相談で確認できてよかった．まあ有名素数1個で投げたら落とされたので1919191991と1919191993にしたんですが．

F

最小包含円を部分問題として含むのでマラソンじゃね？とか言ってたけど言ってただけ．

G

解けるべきだった度No. 1 なんか終盤に取り組んで必要な情報は大体合ってたけど遷移が詰めきれず．いつもだったらkort0nがささっと通してそうな問題．

H

kort0nが死闘を繰り広げていた．つらそうだった．

I

せっかく持ってきたので方眼紙にお絵描きくらいはしてたけど何もわからず…

J

なんかkort0nに頼まれたのでUFと最大流を写経したらサッと通してくれた．

K

しばらく考えると畳み込みなのではい． 2次元FFT書いたことあってよかった．

Day2

https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day2

idsigmaさんが用事とのことでseicaさんが入ってくれた．この日はまあよかった．

A

kort0nがサクッと通してた．

B

まあ似たようなことは考えてはいたけど正当性1ミリもわからないしこれは厳しい．

C

自分が最初に目を通した問題だけど何もわからなかった． kort0nが最小費用流で解けると言い出して解法説明してくれたけど正直いまいちわからなかった． PrimalDualを写経したら通してくれた．天才だと思う．

D

なんか記憶がない．多分kort0nがサクッと通してくれた（？）．

E

seicaさんがギャグであることを見抜いてサクッと通してくれた．

F

seicaさんが考察してくれて一般マッチングになって持ってないし書いたことないので放置されて終了…

G

これもseicaさんが頑張って考察してくれていた．ボス問だとは思わなかった…

H

やりたいと主張してやってたけどわからないのでkort0nに相談して二乗DPを考えてもらう．その式を線形にして期待値は合ったが分散の式が詰めきれずにコンテスト終了．通したかった…

I

これできるわと言ってから10⁹に気づく．でもまあどうせ規則的でしょと予想して投げるけど落ちたので放置．リジャッジで後から通って安心．

J

seicaさんが考察して答えを数式にしてくれた． kort0nが多項式補間と言い出したので書く．偶奇で式が変わることにしばらく気づかず苦戦したがなんとかAC. みんなで通した感があってよかった．

Day3

https://onlinejudge.u-aizu.ac.jp/beta/room.html#JAGSummerCamp19Day3

idsigmaさんとてんぷらさんが作問側ということでチームkaisan（heno_code,kort0n,risujiroh）で参加．優勝やったぜ．

ABC

1人1問担当． FAはなかったが全体としては早かった．

D

自分は何もわからなかったがkort0nが解法と計算量評価をちゃんとしてくれた． henoさんが最後に取り組んでたが間に合わず．

E

最初フロー(？)と聞いてたがhenoさんが落ち着いてDPであることを見抜き通してくれた．ちゃんと考えてないけど多分自分は解けないと思う．

F

部分問題解くのにもケーリーの公式が要るねとなって後回し．難しいけど通せるようになりたい問題．

G

割と得意なタイプの問題．解法を詰めてhenoさんに伝えて通してもらった．

H

kort0nと一緒に考えて最強コン予選Eだねマージテクだねとなりhenoさんに方針を伝える． kort0nが口出ししようとすると実装方針は僕に任せてくださいとのこと．実際に着実に実装して通してくれた．頼もしすぎる．

I

見た目がヤバそうで通されてもないのでしばらく放置されていたが終盤やる問題がなくなったので取り組んだ．行列で書くと三角行列なので簡単に逆行列が求まる．落ち着いて式を書いて睨むと畳み込みの形をしてるのではい（この合宿二度目）． henoさんがEに取り組んでたので合間を縫って自分で書いた． FA嬉しい．

J

開始からkort0nも自分もちょくちょく取り組んでたが通せなかった純粋天才構築パズル．人間に思いつくのは2冪くらいまでですね…

2019-04-15

二項係数が出てくる変な和

に，競プロや数学をしていると時々出会います．
今回は，

$\begin{aligned} \sum _ {i = 0} ^ {m} \frac{(-1) ^ {i}}{n - m + i} \binom{m}{i} = \frac{1}{(n-m) \binom{n}{m}} \end{aligned}$

というものに出会いました．
$m$ に関する帰納法で一応示すことができますがいまいちスッキリしません．
右辺の分母に二項係数があるため組み合わせ的な解釈も難しそうです．
こういうときは母関数を考えてみると上手くいくかもしれません．
左辺をぐっと睨むと多項式を積分して $x = -1$ としたものに見えます．
実際，

$\begin{aligned} f(x) &= (-1) ^ {n - m} x ^ {n - m - 1} \sum _ {i = 0} ^ {m} \binom{m}{i} x ^ {i} \end{aligned}$

とおくと左辺は $F(-1)$ に等しくなります（ $F(x)$ は $f(x)$ の原始関数で定数項が $0$ のもの）．
さらに $F(0) = 0$ なのでこれは $\int _ {0} ^ {-1} f(x) dx$ に等しいです．
また，二項定理を使うと，

$\begin{aligned} f(x) &= (-1) ^ {n - m} x ^ {n - m - 1} (1 + x) ^ {m} \end{aligned}$

とかけるので結局左辺は，

$\begin{aligned} \int _ {0} ^ {-1} (-1) ^ {n - m} x ^ {n - m - 1} (1 + x) ^ {m} dx \end{aligned}$

に等しくなります．
ここで， $t = -x$ と置換するとこの定積分は，

$\begin{aligned} \int _ {0} ^ {1} t ^ {n - m - 1} (1 - t) ^ {m} dt \end{aligned}$

と書けます．
これはなんとベータ関数の積分公式（https://mathtrain.jp/beta）によって計算でき（！），

$\begin{aligned} \int _ {0} ^ {1} t ^ {n - m - 1} (1 - t) ^ {m} dt &= \frac{(n - m - 1)!m!}{n!} \end{aligned}$

となります．
これは右辺に等しいことが簡単にわかるので証明完了です．
母関数ってすごい．

ところでふとWolfram Alpha先生に投げてみたらほとんど同じ式にしてくれました…（完） https://www.wolframalpha.com/input/?i=Sum%5B(-1)%5Ei%2F(n-m%2Bi)*C(m,i),%7Bi,0,m%7D%5D

2019-04-14

AtCoder Grand Contest 032 F - One Third

公式解説より面倒なことをしている気もするが知見が得られたので． atcoder.jp

問題概要

円形のピザに中心から外側に向かってランダムに $N$ 回切込みを入れる．
連続するピースのうち合計面積が $\frac{1}{3}$ （ピザ全体を $1$ とする）に最も近いものを選ぶ．
その面積を $x$ とするとき $|x - \frac{1}{3}|$ の期待値を $\mathrm{mod} \ 10 ^ {9} + 7$ で求めよ．

制約

$2 \leq N \leq 10 ^ {6}$

解法

言い換え

ある切れ込みから $\frac{1}{3}$ 離れた二箇所付近は考慮するが自身の周りは考慮しないというのが考えにくい．
そこで公式解説と同様の言い換えを行う．

$\left[ 0, 1 \right]$ 上にランダムに $N - 1$ 点，色をランダムに赤青緑から選び打つ．
$0$ に赤点， $1$ に青点を打つ．
色の異なる二点間の距離の最小値の期待値を求めよ．

この問題が解ければその $\frac{1}{3}$ 倍が答えとなる．

まず，色のことは忘れて…

$N + 1$ 点の位置を昇順に $X _ 0,...,X _ N \ (X _ 0 = 0, X _ N = 1)$ とする．
距離の最小値としては隣り合う二点のみを考えれば十分である．
そこで， $X _ 1 - X _ 0, \dots ,X _ N - X _ {N - 1}$ を昇順に並び替えたものを $Y _ 1, \dots, Y _ N$ とおく．
実は，この $Y _ k$ の分布関数 $F _ k$ や期待値 $E \left[ Y _ k \right]$ は，

$\begin{aligned} F _ k(x) &= 1 - \sum _ {i = 0} ^ {k - 1} \binom{N}{i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \max \left\{1 - (N - i + j) x, 0 \right\} ^ {N - 1} \ (x \geq 0) \\ E \left[ Y _ k \right] &= \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \end{aligned}$

と表すことができる．

略証

まず，分布関数 $F _ k$ について（以降， $x \geq 0$ とする），

$\begin{aligned} 1 - F _ k(x) &= P \left[ Y _ k \geq x \right] \\ &= P \left[ |\left\{ j \mid 1 \leq j \leq N, X _ j - X _ {j - 1} \geq x \right\}| \geq N - k + 1 \right] \\ &= \sum _ {i = 0} ^ {k - 1} P \left[ |\left\{ j \mid 1 \leq j \leq N, X _ j - X _ {j - 1} \geq x \right\}| = N - i \right] \end{aligned}$

と変形し，各項を包除原理を用いて計算すると，

$\begin{aligned} 1 - F _ k(x) &= \sum _ {i = 0} ^ {k - 1} \binom{N}{N - i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \max \left\{ 1 - (N - i + j) x, 0 \right\} ^ {N - 1} \end{aligned}$

となる．
これを用いると期待値 $E \left[ Y _ k \right]$ は，

$\begin{aligned} E \left[ Y _ k \right] &= \int _ {0} ^ {\infty} 1 - F _ k(x) dx \\ &= \sum _ {i = 0} ^ {k - 1} \binom{N}{i} \sum _ {j = 0} ^ {i} (-1) ^ {j} \binom{i}{j} \frac{1}{N (N - i + j)} \\ &= \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \end{aligned}$

となる（最後の式変形は非自明だ（と思う）が， $i$ に関する帰納法で証明できる）．

（追記）知人の協力によって母関数を考えるとベータ関数の積分公式に帰着されることが判明した．
二項係数が出てくる変な和 - 劣ブログ

仕上げ

$N + 1$ 点によってできた $N$ 個の区間を短い順に見ていき初めて両端の点の色が異なったときの区間の長さ（の期待値）が求めるものとなる．
これは点の位置と色が独立であることから，

$\begin{aligned} \left( \sum _ {k = 1} ^ {N - 1} \left( \frac{1}{3} \right) ^ {k - 1} \frac{2}{3} Y _ k \right) + \left( \frac{1}{3} \right) ^ {N - 1} Y _ N \end{aligned}$

となる．
よって答えを書き下すと，

$\begin{aligned} \frac{1}{3} \left( \left( \sum _ {k = 1} ^ {N - 1} \left( \frac{1}{3} \right) ^ {k - 1} \frac{2}{3} \frac{1}{N} \sum _ {i = 0} ^ {k - 1} \frac{1}{N - i} \right) + \left( \frac{1}{3} \right) ^ {N - 1} \frac{1}{N} \sum _ {i = 0} ^ {N - 1} \frac{1}{N - i} \right) \end{aligned}$

となる．

実装例

https://atcoder.jp/contests/agc032/submissions/4713546