2021-01-14

Xmas Contest 2020 B: Beterminant 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_b

問題概要

$1$ 円払うと $P$ % で $W$ 円もらえる賭けを $n$ 回やって最終的に所持金が増えている確率が $\frac{1}{2}$ を超えるような最大の $n$ を求めよ．存在しない場合や無限個存在する場合はそれを指摘せよ．

考察

$W \ge 2$ として，所持金が増えるのはあたりが $\left\lfloor \frac{n}{W} \right\rfloor + 1$ 回以上出たときです． $\left\lfloor \frac{n}{W} \right\rfloor$ が一定の範囲内では $n$ を増やしてもその確率は減少しないので，条件を満たす最大の $n$ を求めるにあたっては $n = W m - 1$ ( $m$ は正の整数) の形のみ考えればよいです．

所持金の増加の期待値を考えると， $PW \lt 100$ のときはたくさんやったら負けそうで， $PW \gt 100$ のときはたくさんやったら勝てそうです． $PW = 100$ のときは期待値は $0$ ですが， $n = W m - 1$ のとき切り捨てで得をしてそうなのでなんとなく勝てそうです．コンテスト中に正解するためにはこのくらいの考察でほぼ足りるのですが，以下ちゃんとした正当化を与えておきます．

道具

整数 $n, k$ と実数 $p$ ( $n \ge 0$ ， $0 \le k \le n+1$ ， $0 \le p \le 1$ ) に対し， $f(n, k, p) = \sum_{i=0}^{k-1} \binom{n}{i} p^i (1-p)^{n-i}$ と定めます (すなわち，確率 $p$ であたる賭けを $n$ 回やってあたりが $k$ 回未満の確率です)．

Uhlmann [1] により以下の式が示されています：

$f\left(n, k, \frac{k}{n+1}\right) + f\left(n, n+1-k, \frac{n+1-k}{n+1}\right) = 1$ ( $0 \le k \le n+1$ )
$0 = f\left(n, 0, \frac{0}{n+1}\right) \lt f\left(n, 1, \frac{1}{n+1}\right) \lt \cdots \lt f\left(n, n+1, \frac{n+1}{n+1}\right) = 1$
$f\left(n, k, \frac{k-1}{n-1}\right) + f\left(n, n+1-k, \frac{n-k}{n-1}\right) = 1$ ( $n \ge 2$ ， $1 \le k \le n$ )
$1 = f\left(n, 1, \frac{0}{n-1}\right) \gt f\left(n, 2, \frac{1}{n-1}\right) \gt \cdots \gt f\left(n, n, \frac{n-1}{n-1}\right) = 0$ ( $n \ge 2$ )

[1] の論文は記法がちょっと違うしドイツ語だしなので，ここでも証明をまとめておきます．

1. と 3. は $f(n, n+1-k, 1-p) = \sum_{i=0}^{n-k} \binom{n}{i} (1-p)^i p^{n-i} = \sum_{i=k+1}^n \binom{n}{i} p^i (1-p)^{n-i}$ なのでよいです．

ここで， $f$ の $p$ による微分を計算しておきます． $1 \le k \le n$ として， $f'(n, k, p) = -n \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \lt 0$ です ( $f$ が $p$ について単調減少なことは定義の意味から明らかですが)．さらに， $f''(n, k, p) = -n \binom{n-1}{k-1} p^{k-2} (1-p)^{n-1-k} ((k-1) - (n-1) p)$ で，これは $0 \lt p \lt \frac{k-1}{n-1}$ のとき負， $p = \frac{k-1}{n-1}$ のとき $0$ ， $\frac{k-1}{n-1} \lt p \lt 1$ のとき正です．これを $f'$ の評価に用います．

2. について， $f\left(n, 0, \frac{0}{n+1}\right) = 0 \lt f\left(n, 1, \frac{1}{n+1}\right)$ はよいです． $2 \le k \le \frac{n+1}{2}$ のとき， $\frac{k-1}{n+1} \lt \frac{k-1}{n-1} \le \frac{k}{n+1}$ なので，平均値の定理と合わせて，

$\begin{align} &f\left(n, k, \frac{k}{n+1}\right) - f\left(n, k-1, \frac{k-1}{n+1}\right) \\ &= \left(f\left(n, k, \frac{k}{n+1}\right) - f\left(n, k, \frac{k-1}{n+1}\right)\right) + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &\gt \frac{1}{n+1} f'\left(n, k, \frac{k-1}{n-1}\right) + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &= -\frac{n}{n+1} \binom{n-1}{k-1} \left(\frac{k-1}{n-1}\right)^{k-1} \left(1 - \frac{k-1}{n-1}\right)^{n-k} + \binom{n}{k-1} \left(\frac{k-1}{n+1}\right)^{k-1} \left(1 - \frac{k-1}{n+1}\right)^{n-k+1} \\ &= \binom{n}{k-1} \frac{(k-1)^{k-1} (n-k)^{n-k} (n-k+1)}{(n+1)^n} \left(-\left(1+\frac{2}{n-1}\right)^{n-1} + \left(1+\frac{1}{n-k}\right)^{n-k} \left(1+\frac{1}{n-k+1}\right)^{n-k+1}\right) \\ &\gt 0 \end{align}$

です (最後の不等号は $\left(1+\frac{1}{x}\right)^x$ の単調性から従います)．また，偶数 $n$ に対し， $\frac{n/2+1}{n+1} \lt \frac{n/2}{n-1}$ より，

$\begin{align} &f\left(n, n/2+1, \frac{n/2+1}{n+1}\right) - f\left(n, n/2, \frac{n/2}{n+1}\right) \\ &= \left(f\left(n, n/2+1, \frac{n/2+1}{n+1}\right) - f\left(n, n/2+1, \frac{n/2}{n+1}\right)\right) + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &\gt \frac{1}{n+1} f'\left(n, n/2+1, \frac{n/2+1}{n+1}\right) + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &= -\frac{n}{n+1} \binom{n-1}{n/2} \left(\frac{n/2+1}{n+1}\right)^{n/2} \left(1 - \frac{n/2+1}{n+1}\right)^{n/2-1} + \binom{n}{n/2} \left(\frac{n/2}{n+1}\right)^{n/2} \left(1 - \frac{n/2}{n+1}\right)^{n-n/2} \\ &= 0 \end{align}$

です．これで「中央とその手前」のすべての不等号が示され，残りは 1. より得られます．

4. について， $1 \le k \le n-1$ として，

$\begin{align} &f\left(n, k+1, \frac{k}{n-1}\right) - f\left(n, k, \frac{k-1}{n-1}\right) \\ &= \left(f\left(n, k, \frac{k}{n-1}\right) - f\left(n, k, \frac{k-1}{n-1}\right)\right) + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &\lt \frac{1}{n-1} f'\left(n, k, \frac{k}{n-1}\right) + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &= -\frac{n}{n-1} \binom{n-1}{k-1} \left(\frac{k}{n-1}\right)^{k-1} \left(1 - \frac{k}{n-1}\right)^{n-k} + \binom{n}{k} \left(\frac{k}{n-1}\right)^k \left(1 - \frac{k}{n-1}\right)^{n-k} \\ &= 0 \end{align}$

なのでよいです．

議論

$W \le 1$ のときは所持金が増えないので条件を満たす $n$ は存在しません．以下 $W \ge 2$ とします．また， $p = \frac{P}{100}$ とおきます．

$W \ge 2$ より $m \le \frac{(Wm-1) + 1}{2}$ です．

3. と 4. より，正の整数 $m$ に対し $f\left(Wm-1, m, \frac{m-1}{(Wm-1)-1}\right) \ge \frac{1}{2}$ です． $pW \lt 1$ のとき， $m \ge \frac{1-2p}{1-pW}$ のとき $p \le \frac{m-1}{(Wm-1)-1}$ なので， $f(Wm-W, m, p) \ge \cdots \ge f(Wm-2, m, p) \ge f(Wm-1, m, p) \ge \frac{1}{2}$ が得られます．よって，各 $m \lt \frac{1-2p}{1-pW}$ に対し $n = Wm-1$ を条件を満たす候補として調べればよいです．制約下での $\frac{1-2p}{1-pW}$ の最大値は， $(p, W) = \left(\frac{1}{100}, 99\right)$ のときの $98$ です (ちなみに，このように得られた評価は少し緩く，実際に条件を満たす $n$ の最大値はこのとき $3167 = 99 \cdot 32 - 1$ です)．

一方，1. と 2. より，正の整数 $m$ に対し $f\left(Wm-1, m, \frac{m}{(Wm-1)+1}\right) \le \frac{1}{2}$ です． $pW \ge 1$ のとき， $p \ge \frac{1}{W} = \frac{m}{(Wm-1)+1}$ なので $f(Wm-1, m, p) \le \frac{1}{2}$ が得られます．ここですべての等号が成り立つのは $p = \frac{1}{W}$ かつ $m = \frac{(Wm-1)+1}{2}$ のとき，すなわち $(p, W) = \left(\frac{1}{2}, 2\right)$ の場合であり，そうでない場合はこれで無限個の $n = Wm - 1$ が条件を満たすことがわかりました．

$(p, W) = \left(\frac{1}{2}, 2\right)$ の場合は， $f\left(n, \left\lfloor\frac{n}{2}\right\rfloor+1, \frac{1}{2}\right)$ は $n$ が偶数のとき $\frac{1}{2}$ より大きく $n$ が奇数のときちょうど $\frac{1}{2}$ であることが簡単にわかります．よって条件を満たす $n$ は存在しません．

実装

多倍長整数を使って $f\left(n, \left\lfloor\frac{n}{W}\right\rfloor, \frac{P}{100}\right)$ を計算する (最初に $(100-P)^n$ を計算し，二項係数などをひとつずつ求めていく) のが確実です．浮動小数点数で適切に計算 (階乗の $\log$ などをとる) してぎりぎりになるケースは実際には制約下にはありません．ちなみに，有理数 $p \ne \frac{1}{2}$ に対し $f(n, k, p) \ne \frac{1}{2}$ らしいです [2]．

$n$ 回中 $i$ 回あたる確率を DP で求めていってもよいです (誤差も小さいです)． $n = Wm - 1$ のみ考えるという考察すらスキップ可能です．あたりが少ないほうだけ調べる (つまり，所持金が増えない確率を計算する)，答えを埋め込むなどをしないと時間制限は厳しいかもしれません．

注意を要するのは条件を満たす $n$ が無限個存在するかの判定です．場合分けをする場合は $(P, W) = (50, 2)$ を忘れない必要があります．実験的に行う場合は，「適当に大きい $n$ で成り立たなかったら無限個存在はしない」としてしまうのは誤りで，ちゃんと $n = Wm - 1$ を見たり前後 $W$ 個程度を見たりすることになります．

統計情報

正解者：チーム人任せ (0:45:20) はじめ 31 チーム

厳密な証明をしなくてもそれっぽくやれば正解できる (ただし考察が雑なほど一部のケースではまる)
整数パーセントなことが本質的な制約 (そして出てくる答えの上限は案外 (?) 大きい)

という特徴の問題でした．1 つ目のために普通のコンテストには出しにくい問題ですが，クリスマスにはとっつきやすい枠としてよさそうという気持ちで出題しました．結果としては順位表を赤く染め上げてしまいました……．ここまでは予想外でしたが，一発 AC の方はとても丁寧だと思います．

ところで， $P W \lt 100$ のときに $n = W m - 1$ だけ考えると所持金が増える確率が単調減少ということも実験的に気づきました．このことを使った人もいるかもしれません．これについては証明が思い浮かなかったので，証明あるいは反証を募集しています． $P W \ge 100$ のときに様子が異なるので，上で示した Uhlmann の結果よりも大変そうと考えています．

参考文献

[1] Uhlmann, W. Ranggrößen als Schätzfunktionen. Metrika 7, 23–40 (1963).

[2] Nowakowski, Szymon. "Uniqueness of a Median of a Binomial Distribution with Rational Probability." arXiv preprint arXiv:2004.03280 (2020).

2020-01-03

Xmas Contest 2019

Xmas Contest 2019 にご参加いただいた皆様，どうもありがとうございました！

大変遅くなりましたが解説記事が準備できました．今年も相変わらずのばたばた準備をしていましたが，いつの間にか問題がいくつも分裂してすごいことに．皆様何かしら楽しめる問題を見つけていただければ幸いです．

わたしが原案を出した問題の解説はこちらです．

それ以外の問題へのコメントはこちらです．

A: 適当に隣接具合調べるプログラム書いた後は HTML でせっせと並べてました．1 時間くらい．
B: これ個人的に Xmas Contest っぽさを感じる構築でよい．解くのは google ですんなり．
F: 似て非なる問題がよくある気がするのではまりがちかもしれません．
G: きれいな出題．
H: writer 陣揃って data structure．
I: 横位置を揃えて必死に DP みたいなのを考えていました．データミス申し訳ありません (clar をご確認ください)．
L: 単語リストがわかる勢ですがちゃんとプログラム書いてちゃんとはまってました．

2020-01-03

Xmas Contest 2019 K: Set of Trees

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_k

問題概要

根付き木の順序を，子を降順に並べたものの辞書順として再帰的に定める．根付き木がいくつかあって， $1$ つ選んで「小さく」するという行動ができる $2$ 人ゲームを考える．初期状態が与えられるので，先手必勝か後手必勝かゲームが無限に続くかを判定せよ．

こたえ

盤面の根付き木を $T_1, \ldots, T_l$ とし， $T_i = \{\!\!\{T_{i,1}, \ldots, T_{i,k_i}\}\!\!\}$ とします．後手が勝つ条件は「任意の根付き木 $X$ について， $T_{i,1}, \ldots, T_{i,k_i}$ のうち $X$ と同型なものの個数を $a_i$ としたとき， $a_1 \operatorname{XOR} \cdots \operatorname{XOR} a_l = 0$ である」です．そうでないときは先手が勝ちます (必ず終わります)．このことを後ほど説明していきます．

実装

根付き木を整数に対応させる単射を用意すればよいです．部分木の頂点数が少ない順あるいは最大深さが小さい順などで頂点を見て，

map := 整数列から整数への連想配列
num := 0
foreach 頂点 u:
  v_1, ..., v_k := u の子
  f(v_1) >= ... >= f(v_k) となるようにソート
  if [f(v_1), ..., f(v_k)] !in map:
    map[[f(v_1), ..., f(v_k)]] := num
    num += 1
  f(u) := map[[f(v_1), ..., f(v_k)]]

というように f(u) を定めていけばよいです．この問題の入力形式なら頂点番号が大きい順でも OK です．時間計算量は，次数 $d$ の頂点で $O(d \log N)$ なので全体で $O(N \log N)$ です．

根付き木に対する適切なハッシュ関数をとってもよいです．こちらなどを参照．

順序数

順序数とそれらの演算が出てきます．ある程度既知として進めるのでちゃんとやるのは他の文献に任せます．演算の定義とかはこれで行きます：

順序数は， $0 = \{\}$ と，何かの successor であるもの $\alpha = \beta \cup \{\beta\}$ と，そうではないもの (limit) $\alpha = \sup \alpha$ に分かれる．
- $= \alpha$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cup \{\alpha + \gamma\}$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha + \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 0$ ( $\beta = 0$ のとき)
- $= (\alpha \cdot \gamma) + \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha \cdot \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 1$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cdot \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha^\gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)

これらの演算は非可換です．

考察

不偏ゲームなので，Grundy 数を (考えられるなら) 考えたいです．局面 $G$ の Grundy 数 $g(G)$ は， $G$ から $1$ 手で進める局面 $G'$ によっては $g(G')$ と書けないような最小の順序数です．いくつか例をやってみると ( $\{\!\!\{$ , $\}\!\!\}$ を [, ] で書いています) 次のようになります．

g([]) = 0
g([[]]) = 1
g([[], []]) = 2
g([[], [], []]) = 3
g([[[]]]) = ω

[[[]]] からは任意の非負整数に進めるので， $\{0, 1, \ldots\} = \omega$ です．

g([[[]], []]) = ω + 1

任意の自然数あるいは $\omega$ に進めるので， $\{0, 1, \ldots\} \cup \{\omega\} = \omega + 1$ です．

g([[[]], [], []]) = ω + 2
g([[[]], [], [], []]) = ω + 3
g([[[]], [[]]]) = ω・2
g([[[]], [[]], []]) = ω・2 + 1
g([[[], []]]) = ω^2
g([[[], [], []]]) = ω^3
g([[[], [], []], [[], []], [[], []], [], [], [], []]) = ω^3 + ω^2・2 + 4
g([[[[]]]]) = ω^ω

こんな感じになるので，次のことが予想できます：根付き木 $T = \{\!\!\{T_1, \ldots, T_k\}\!\!\}$ ( $T_1 \ge \cdots \ge T_k$ ) に対し $g(T) = \omega^{g(T_1)} + \cdots + \omega^{g(T_k)}$ と定めると， $T \gt T'$ ならば $g(T) \gt g(T')$ であり，また， $g(T) \gt \alpha$ ならば $g(T') = \alpha$ なる $T'$ が存在する．

前半は， $T' = \{\!\!\{T'_1, \ldots, T'_l\}\!\!\}$ ( $T'_1 \ge \cdots \ge T'_l$ ) について $T_1 = T'_1,\, \ldots,\, T_{j-1} = T'_{j-1},\, T_j \gt T'_j$ のときには $\omega^{g(T_j)} \ge \omega^{g(T'_{j'})+1} = \omega^{g(T'_{j'})} \cdot \omega \gt \omega^{g(T'_{j'})} \cdot (l - j + 1) \ge \omega^{g(T'_j)} + \cdots + \omega^{g(T'_l)}$ なことを使うとできます．後半は丁寧にやると面倒なので省略するのですが，有名事実を用いて理解することができます．

すべての順序数 $\alpha$ は $\beta_1 \ge \cdots \ge \beta_k$ を用いて $\alpha = \omega^{\beta_1} + \cdots + \omega^{\beta_k}$ という形で一意に書けます．これは Cantor 標準形と呼ばれています． $\alpha \lt \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ ならば $\alpha \gt \beta_j$ なので，再帰的に展開していくことでそのような順序数がちょうど根付き木に対応していて，順序数としての順序がこの問題で定めた順序と一致することがわかります．つまりこの問題は， $\omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ 未満の順序数を根付き木の形で見せていただけなのでした．

順序数は整列集合なので，何をどうやってもゲームが無限に続くことはありません．よって Sprague–Grundy の定理が適用できて，盤面に根付き木 $T_1, \ldots, T_l$ が並んでいるときの Grundy 数は $g(T_1) \operatorname{XOR} \cdots \operatorname{XOR} g(T_l)$ となります．あとは XOR をどう計算するかだけですが， $\omega = 2^\omega$ なので $g(T_i) = 2^{\omega \cdot g(T_{k_1})} + \cdots + 2^{\omega \cdot g(T_{k_i})}$ となり， $\alpha \gt \beta \implies \omega \cdot \alpha \ge \omega \cdot \beta + \omega$ を用いると，最初に述べたように同型なものたちごとに数えればよいことがわかります．

統計情報

正解者：TSG さん (3:03:45)，kimiyuki さん (3:38:23)

Grundy 数に無限順序数が出てくる問題，ごくごく稀にある気がしますが，なかなかコンテストの問題にしづらいんですよね．Cantor 標準形が根付き木に見える→解法は同型判定だけでいい，というのが面白かったので出題してみました．

2020-01-03

Xmas Contest 2019 J: Sub-Post Correspondence Problem

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_j

問題概要

文字列 $A_1, B_1, \ldots, A_N, B_N$ が与えられるので，ある $i_1, \ldots, i_k$ ( $k \gt 0$ ) に対して $B_{i_1} \cdots B_{i_k}$ が $A_{i_1} \cdots A_{i_k}$ の連続とは限らない部分列となるようにできるか判定せよ (一応，同じ添え字は $2019^{2019}$ 回まで)．

解法

カード $1$ 枚での解 ( $k = 1$ ) があれば YES でなければ NO です．なぜなら， $b b'$ が $a a'$ の部分列ならば， $b$ が $a$ の部分列であるか $b'$ が $a'$ の部分列であるかだからです ( $a$ と $a'$ の境界に対応する場所は $b$ と $b'$ の高々一方にしか入ってこないので)．

$k = 1$ のときの判定は， $B_i$ の文字を $1$ 文字ずつ， $A_i$ の中に貪欲にとっていけば線型時間でできます．

統計情報

正解者：siotouto さん (0:13:54) はじめ 95 チーム

ギャグ枠です． $N \le 16$ はフェイクです．

Post の対応問題は決定不能な問題の中でもパズルっぽい見た目ということで人気があります (?)．問題設定を少し変えた亜種は結構研究されているらしく，決定不能と決定可能の間が見えてくるのが面白いですね．

2020-01-03

Xmas Contest 2019 E: Sum of f(n) 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_e

問題概要

$n$ の素因数の個数 (重複込み) を $f(n)$ とする． $N$ が与えられるので $\sum_{n=1}^N f(n)$ を求めよ．

解法 1 (?)

答えを手元で全部計算して，適当な間隔で区切って埋め込みます．狭い区間については区間篩のアルゴリズムで $f$ を効率的に計算できる (素数 $p$ で篩うときに $p$ で割り切れる回数だけ $1$ を足す) ので，これで正解することができます．

終わる確信があったら，手元で D 問題と一緒に計算するとよいと思います！　D 問題より桁数が多かったり時間制限が短かったりでちょっとだけ大変かもしれません．

解法 2

素数 $p$ の影響が何回足されるかを考えると，各 $p$ について， $N$ 以下の $p$ の倍数の個数， $p^2$ の倍数の個数， $p^3$ の倍数の個数，……を足していけば答えになります． $p^2$ 以降の倍数が現れるのは $p \le \sqrt{N}$ なもののみなので，それらについてはひとつずつ処理できます．これで，あとは $\sum_{p:素数} \lfloor\frac{N}{p}\rfloor$ を求めればよくなりました．

$\lfloor\frac{N}{p}\rfloor$ の値は $2 \sqrt{N}$ 通りくらいしかないので，同じ値になる部分をまとめて計算したいです． $\lfloor\frac{N}{p}\rfloor = k \iff \lfloor\frac{N}{k+1}\rfloor \lt p \le \lfloor\frac{N}{k}\rfloor$ なので，「 $\lfloor\frac{N}{k}\rfloor$ 以下の素数の個数」という形のものが数えられれば， $\sum_p \lfloor\frac{N}{p}\rfloor = \sum_k (\pi(\lfloor\frac{N}{k}\rfloor) - \pi(\lfloor\frac{N}{k+1}\rfloor)) k$ と計算できます ( $\pi(n)$ は $n$ 以下の素数の個数)．

これは，賢い DP をするとできます．素数を小さい順に $p_1, p_2, \ldots$ とします． $g(i, n)$ を， $n$ 以下の正の整数であって $p_1, \ldots, p_i$ のいずれでも割り切れないものの個数とおきます． $g(i, n) = g(i - 1, n) - g(i - 1, \lfloor\frac{n}{p_i}\rfloor)$ という漸化式が成り立ちます． $\pi(n) = g(\pi(\sqrt{n}), n) - 1$ なので， $\pi(\lfloor\frac{N}{k}\rfloor)$ の形のものを計算するのに必要な $g(i, n)$ はやはり $n = \lfloor\frac{N}{k}\rfloor$ の形をしています．

このままだとまだ遅いので高速化します． $g(i - 1, n)$ から $g(i, n)$ への変化に注目すると， $n \lt p_i$ では変わらず， $p_i \le n \lt p_i^2$ では $1$ 減るだけになっています．ということをふまえて $g'(i, n) = g(i, n) + \min\{i, \pi(n)\}$ とおき直すと， $n \lt p_i^2$ では $g'(i, n) = g'(i - 1, n)$ ， $n \ge p_i^2$ では $g'(i, n) = g'(i - 1, n) - g'(i - 1, \lfloor\frac{n}{p_i}\rfloor) + i$ となります．これで DP 配列を使い回して $n \ge p_i^2$ の部分のみ更新すればよいことになります．なお， $g'(i, n)$ は $n$ 以下の正の整数に対して Eratosthenes の篩で $p_1, \ldots, p_i$ を処理したときに残るものの個数になっています．

時間計算量を見積もると，更新箇所の個数が

$1 \le i \le \pi(N^{1/4}) \sim N^{1/4} / \log N$ についてそれぞれ $O(N^{1/2})$ 個
$\pi(N^{1/4}) \lt i \le \pi(N^{1/2})$ について合計で $O\left(\frac{1}{\log N} \int_{N^{1/4}}^{N^{1/2}} \frac{N}{x^2} dx\right) = O(N^{3/4} / \log N)$ 個

となり (素数の密度についての定理を用いました) 全体で $O(N^{3/4} / \log N)$ 時間となります．これで $100$ 点がとれます．

なお，素数の個数 $\pi$ の計算については，より高速なアルゴリズムも知られています．

統計情報

45 点：1 チーム

100 点：team_2019 さん (29:26) はじめ 7 チーム

実は冒頭のストーリーは結構実話に近く，D 問題を提案しようとしたら書き間違えて，わたしが気づかないまま snuke さんが解いてくれて答えの大きさを見て気づいてわたしも解きました．高速素数カウントは初めて実装したので勉強になりました！

2020-01-03

Xmas Contest 2019 D: Sum of (-1)^f(n) 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d

問題概要

$n$ の素因数の個数 (重複込み) を $f(n)$ とする． $N$ が与えられるので $\sum_{n=1}^N (-1)^{f(n)}$ を求めよ．

解法 1 (?)

答えを手元で全部計算して，適当な間隔で区切って埋め込みます．狭い区間については区間篩のアルゴリズムで $f$ を効率的に計算できる (素数 $p$ で篩うときに $p$ で割り切れる回数だけ $-1$ 倍する) ので，これで正解することができます．

$45$ 点は割と易しめだと思います． $100$ 点は結構な計算資源を使うかなと思っていたので，解けちゃってもいいかなという感じでした．何なら昔の問題にリンクを貼っていて，パソコンを使いましょうというのを伝えていた感じだったかもしれません．

解法 2

$\lambda(n) = (-1)^{f(n)}$ とおきます．突然ですが，正の整数 $n$ に対し， $\sum_{d|n} \lambda(d)$ は $n$ が平方数のとき $1$ ，そうでないとき $0$ です．理由は例えば $n = 2^3 \cdot 3^4$ なら

    3^0 3^1 3^2 3^3
2^0  +1  -1  +1  -1
2^1  -1  +1  -1  +1
2^2  +1  -1  +1  -1

みたいな感じで多次元の格子点を市松模様で塗るのを考えてみるとわかります． $\lambda$ は Liouville 関数として知られていて，Wikipedia にもこの式は載っています．もうちょっと突然でない導き方については後述します．

さて， $L(N) = \sum_{n=1}^N \lambda(n)$ を求めたいわけですが， $\sum_{d|n}$ みたいなのを見たら累積和をとるという知る人ぞ知る典型テクニックがありまして， $\sum_{n=1}^m \sum_{d|n} \lambda(d) = \sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor)$ となります ( $\frac{n}{d}$ を先に固定して和をとるとわかります)．一方 $n$ が平方数なら $1$ というのを $1 \le n \le m$ で和をとると $\lfloor\sqrt{m}\rfloor$ なので， $\sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor) = \lfloor\sqrt{m}\rfloor$ が得られました．これを $L(m) = \lfloor\sqrt{m}\rfloor - \sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ と書くと $L$ の漸化式を得たことになります．

この形の漸化式をどうするかも知る人ぞ知る典型テクニックなのですが， $L(N)$ を計算するのに必要な $L$ の値は $L(\lfloor\frac{N}{k}\rfloor)$ の形だけになっていて ( $\left\lfloor\frac{\lfloor\frac{N}{k}\rfloor}{k'}\right\rfloor = \lfloor\frac{N}{k k'}\rfloor$ に注意)，異なる $\lfloor\frac{N}{k}\rfloor$ の値は $2 \sqrt{N}$ 通りくらいしかありません． $\sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ の計算は同じ $\lfloor\frac{m}{k}\rfloor$ の値のものをまとめることで $O(\sqrt{m})$ 時間でできるので，

$1 \le m \le \lfloor\sqrt{N}\rfloor$ について $L(m)$ を求めるのに $O(\sqrt{\sqrt{N}}) \times \sqrt{N} = O(N^{3/4})$ 時間
$1 \le k \le \lfloor\sqrt{N}\rfloor$ について $L(\lfloor\frac{N}{k}\rfloor)$ を求めるのに $O\left(\int_{k=1}^{\sqrt{N}} \sqrt{\frac{N}{k}}\right) = O(N^{3/4})$ 時間

となり，全体で $O(N^{3/4})$ 時間の解法が得られました．実装によりますが $45$ 点の想定です．メモ化再帰で連想配列の類を使うと実行時間がちょっと厳しいかもしれません (配列 $2$ つでできます)．

さらなる高速化ですが，小さい方の答えを定義に戻って計算します．Eratosthenes の篩を用いると $1 \le m \le M$ について $L(m)$ を求めるのが $O(M \log \log M)$ 時間でできます．大きい方は $k \le \frac{N}{M}$ まででよくなって $O(N^{1/2} M^{-1/2})$ 時間になるので， $M = (N / \log \log N)^{2/3}$ くらいにとるのがよく， $O(N^{2/3} (\log \log N)^{1/3})$ 時間解法が得られました (高速な篩を用いれば $O(N^{2/3})$ 時間)．これで $100$ 点です．

Dirichlet 級数

最初に天下った部分の話です． $\lambda$ は乗法的関数なので，(形式的) Dirichlet 級数を考えてみたくなりますね！　Euler 積の形で計算すると， $\sum_{n=1}^\infty \lambda(n) n^{-s} = \prod_{p:素数} (1 - p^{-s} + p^{-2s} - \cdots) = \prod_p \frac{1}{1 + p^{-s}} = \prod_p \frac{1 - p^{-s}}{1 - p^{-2s}} = \frac{\zeta(2 s)}{\zeta(s)}$ となり Riemann の $\zeta$ 関数で表すことができました． $\zeta(s)$ をかけるという操作は $\sum_{d|n}$ をとることに対応していて， $\zeta(2 s)$ は平方数だけ $1$ な級数を表しているので，先ほど使った式が示せました．この辺の話は，例えば maspy さんの HP で丁寧に解説されています．

さっきやった方法は Liouville 関数に限った話ではなく，累積和が簡単に書けている数論的関数を $\zeta(s)$ で割ったもの (つまり，Möbius 変換したもの) の累積和を高速に求める一般的な手法になっています．なので，Möbius 関数 $\mu$ や Euler の $\varphi$ 関数なんかの累積和も同様に高速に求まります (それらのほうがたぶん有名なので， $\mu$ の累積和に帰着させて解くという方針も見られました)．

統計情報

45 点：3 チーム

100 点：chocorusk さん (1:00:49) はじめ 6 チーム

Project Euler の回し者ですか？　はい……．数学寄りの問題が集まっているサイトですが，この手の sublinear algorithm の数論問題もたくさんあります．解法共有は正解者のみという文化なので，皆さんもぜひ頭 and/or パソコンを駆使して問題を解いていきましょう．

テストデータには，制約内で答えが最大になる $L(906\,316\,571) = 829$ が (無意味に) 入っています．この関数の漸近的な振る舞いは，かなり謎に満ちてますね……．

2020-01-03

Xmas Contest 2019 C: Sokoban 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_c

問題概要

倉庫番の盤面が与えられるので (入力公開)，解くのに必要な最小手数を求めよ．

sample, 01, 02

小さいので，手で遊んで解けます．しかし，解くだけなら簡単ですが最小手数は非自明だったりします．コンテストでは，見つかった解から $1$ 手ずつ減らして提出してみるのもありだと思います．

確実なプログラミング解ももちろん可能で，盤面の状態数を考えてみると，たとえば 02 ではうさぎの位置は $33$ 通り，そのそれぞれに対し箱の位置が $\binom{32}{4}$ 通り，と抑えられて，特に枝刈り等せずとも BFS で最小手数を求めることができます．

01 は，解くだけなら本当に簡単なのを適当に作ってみました． $23$ 手の解がとても見えやすいと思いますが，うまいことやると減って不思議です．

02 は，左上の空間を利用できる問題を作ってみました (パズルとしての問題ならよくありそう)．左上に何度も行くのをやめるのが大事でそれをすると $69$ 手の解が見えやすいと思うのですが，やっぱりうまいことやると減って，よくわかりません……．ちなみに最後に片づく荷物が左上か右下しかありえないので，奇数手であることがわかって提出を少し節約できたりします．

03

荷物が壁の直角の隅に置かれてしまうと，そこがゴールでない限り詰んでしまいます．このことから，入力にたくさん現れる

###########
####....###
...#.##....
##.@..#####
###...#####
###########

という部分が一方通行の役割を果たすことがわかります (上の図の向きでは左から右へのみ，一定の手数で，荷物の位置を変えずに通れます)．入力の右下の荷物を片付けに行けばよいので， $3 \times 3$ の部屋のようなものを頂点とした最短路問題として解くことができます．

04

$11$ 列ごとに

###########
########...
##...##.@..
#.@..##.#.#
..#.###.#..
#.#.@.@..##
#..#...#.##
##.#.....##
#.@####.#..
#....##..@.
#..#...##..
###..#.##@.
##.@##.....
##....###..
##..#.#####
#####.#####
...........
###########

というパターンが繰り返される構造になっています．左から右へ抜けたいのですが，そのためには右下を回って箱を一度ずらす必要があり，そうすると一旦下から出て一番左まで戻らないといけません．よって，右から $1$ 番目のブロックを左から右へ抜けるためには $2$ 回来なければならない，そのそれぞれに対して右から $2$ 番目のブロックを左から右へ抜けるために $2$ 回ずつ， $4$ 回来なければならない，そのそれぞれに対して……，というようにして，右から $i$ 番目のブロックに $2^i$ 回来なければなりません．これに，各ブロックでかかる手数 (手で遊んで数えるのがよいと思います) を掛けて足すことで答えが求まります．

この入力は，盤のサイズに対して指数手数かかる例になっています．手でクリアしようとすると絶望を感じられると思います．

05

03 で使われていた一方通行のパターンが荷物が片付いていない状態で登場しています．左上の部分は最後に訪れないといけないので，グラフの問題で言い換えると「すべての辺を少なくとも $1$ 回通ってスタート位置に戻ってくるための最小コスト」を求める問題になっています．

これは，(有向) 中国人郵便配達問題として知られた問題です．辺を通る回数分増やして考えると，すべての辺をちょうど $1$ 回ずつ通ってスタート位置に戻って来られる条件は (グラフが強連結かつ) すべての頂点の出次数と入次数が等しいことです (Euler circuit)．ということで，最初のグラフに辺を足して出次数と入次数を等しくする問題と言い換えられますが，その最小コストは入次数が余っている点から出次数が余っている辺へ流す最小費用流問題を解くことで求めることができます．

omake

html にのみ入っているこのデータ，パズルガチ勢であるところのすぬけさんが作りました．最短手数の証明が怪しくて出題を見送ったのですが，参加者の方によってすごく縮められていて，こわいです．わたしは，解けません．

統計情報

得点 01 02 03 04 05 人数
 100  o  o  o  o  o    1
  60  o  o  o  o       7
  43  o  o     o       8
  35  o  o  o          6
  18  o  o            39
  11     o             5
   7  o               53

正解者：DEGwer さん (2:39:03)

倉庫番の盤面が与えられたとき解の有無を判定する問題は PSPACE 完全であることが知られています．倉庫番のパーツを作って Turing machine をエミュレートするという証明です．この論文の見どころは，平面交差です．

そんなわけで実質任意の決定可能問題は倉庫番で表せるのですが，自然なのはグラフの問題で，その中でコンテストであまり頻繁には見かけない (気がする) 郵便配達が思いついたので出してみたくてこのような形になったのでした．