Lucasの定理をPythonで実装する。

Google Code Jam 2021 Qualification Round の各問題で部分点を取って予選通過する方法を解説する。これだけで37点取れるので、予選通過に必要な30点を越え、Round 1A に進める。

重み付き無向グラフで、すべての辺を通る閉路のうち最短経路の距離を求める。

無向グラフについて、頂点を共有しない完全部分グラフの最小個数を求める。

各頂点に整数が書かれた木に対して、クエリを処理していく。各クエリでは辺$(a,b)$と整数$x$が与えられ、$a$から$b$を通らずに到達できるすべての頂点に$x$を足し、最終的に各頂点に書かれた整数を答える。

障害物の置かれたグリッド上で飛車が2回で移動できる範囲を求める。

$1, \ldots, n$ を並び替えた数列を、隣同士の入れ替えを適当な順番でちょうど1回ずつ行ってもとに戻すことが可能か判定する。

フローネットワークの最大流を求めるアルゴリズムとして知られるFord-Fulkerson法の実装を理解するのに苦労したので、できるだけ処理の過程がわかりやすいような実装を試みる。

いわゆる巡回セールスマン問題．$n$ 個の点の間に移動コストが定められていて，点 $0$ から出発し，すべての点を通って点 $0$ に戻ってくるときの最小コストを求める．($n \leq 17$)

各 $i = 1, \ldots , n$ について確率変数 $X _ {i}$ が独立に $[L _ {i}, R _ {i}]$ 上の一様分布に従うとき，$Y = \mathrm{max} \{ X _ {1} , \ldots , X _ {n} \}$ の期待値を求める．

$n \times n$ のグリッドの行または列を選択し，すでに塗られているマスに到達するまでマスを塗りつぶすという操作を $q$ 回行い，最終的に塗られていないマスの数を求める．( $n,q \leq 2 \times 10 ^ {5}$ )

$1$ 回に移動できるマスの数の集合 $S$ が $k$ 個の区間の和集合として与えられたとき，マス $1$ からマス $n$ までの移動の仕方が何通りあるか求める．($k \leq 10, n \leq 2 \times 10 ^ 5$)

$a _ 1 = x, \ a _ {n + 1} = a _ {n} ^ 2\ (\mathrm{mod}\ m)$ で定まる数列 ${ a _ n }$ について，第 $n$ 項までの和を求める．($n \leq 10 ^ {10}, m \leq 10 ^ {5}$)

整数からなる配列が与えられたとき，「どの2つをとっても互いに素」になっているかを判定する．

言語は Kotlin，データベースは MySQL を使う．

multipart/form-data形式で画像データをPostすると，その画像にアクセスできるURLが返ってくるようにする．

コンパクトで距離化可能な位相空間 $X$ 上の連続関数全体の空間 $C(X)$ は一様収束位相に関して可分である．

距離空間上に定義された一様連続関数は完備化した空間上の一様連続関数に一意的に拡張できる．

概要 位相が強くなると， 点列は収束しにくくなる 出ていく写像が連続になりやすく，入ってくる写像が連続になりにくくなる ハウスドルフになりやすくなる コンパクトになりにくくなる 可分になりにくくなる

問題 座標平面上に置かれた $n$ 個の点について，重み $P _ i$ と 座標 $(X _ i, Y _ i)$ をもつとし，点 $i$ から最も使い直線との距離を $D _ i$ とする．直線 $X = 0, Y = 0$ がある状態から始めて，各 $k = 0, \ldots, n$ について，$X$ 軸または $Y$ 軸…

問題 長さ $n$ の数列 $A$ と $q$ 個のクエリが与えられる．各クエリにおいて，与えられた区間における $A _ i$ の種類数を答えよ．( $1 \leq n, q \leq 5 \times 10 ^ {5}$, $1 \leq A _ i \leq n$ )

概要 「ベイズ統計の理論と方法」p116で、正規確率過程を和の形に分解するところについての補足。テキストでは一般の有限次元空間上の確率過程を扱っているが、ここでは簡単のため1次元の場合を考える。同様の議論で拡張できるはず。

概要 slackのメッセージ入力欄で、/user_channel @{user_name} と入力すると、@{user_name} が所属しているパブリックチャンネル一覧を自分だけに表示できるようにする。

問題 整数 $n$ が与えられる。$a _ i > b _ i \geq 0$, $\sum _ {i = 1} ^ {k} (a _ i + b _ i) \leq n$ をみたす $k$ 組の整数のペア $(a _ i, b _ i)$ すべてについて $\prod _ {i = 1} ^ {k} (a _ i - b _ i)$ の総和を求めよ。($n \leq 10 ^ 9, k = 5$)

問題 $n$ 頂点の木が与えられる。$f(i,j)$ を $i \leq j$ なる頂点からなる部分グラフの連結成分の個数とし、$\sum _ {i \leq j} f(i,j)$ を求めよ。

問題 与えられた $n$ 個の整数 $A _ {1}, \ldots, A _ {n}$ から $k$ 個選ぶとき、選んだ要素の積としてありえる値の最大値を求めよ（$1 \leq k \leq n \leq 2 \times 10 ^ 5$）

問題 $ m $ 人の応募者と $n$ 個の商品があり、応募者 $i$ の商品 $j$ に対する希望度 $A _ {ij} \geq 0$ が定まっている。商品 $j$ は $L _ j > 0$ 個しかなく、$1$ 人の応募者に $2$ 個以上の商品が当選することはないとする。 また、希望度が $0$ の商品…

問題 26種類のコンテストを365日間にわたって1日1種類ずつ開催する。$i$ 日目にコンテスト $j$ を開催したとき $S _ {ij}$ の満足度を得て、コンテスト $j$ を開催しなければ $C _ {j} \times (i - L _ {ij})$ の満足度を失う。ただし、$L _ {ij}$ は $i$ 日…

概要 「ベイズ統計の理論と方法」8章の経験過程についての解説。

確率密度関数の各点収束から確率変数の分布収束を導く。