Ford-Fulkerson 法

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

ABC 180 E - Traveling Salesman among Aerial Cities

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

HHKB 2020 F - Random Max

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

ABC 179 F - Simplified Reversi

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

ABC 179 D - Leaping Tak

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

ABC 179 E - Sequence Sum

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

ABC 177 E - Coprime

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

Spring Boot で Entity からテーブルを自動生成するのに必要な設定

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

Kotlinで画像のアップロード

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

C(X)の可分性について

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

一様連続関数を完備化した空間に拡張する

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

強い位相，弱い位相

概要

位相が強くなると，

1. 点列は収束しにくくなる
2. 出ていく写像が連続になりやすく，入ってくる写像が連続になりにくくなる
3. ハウスドルフになりやすくなる
4. コンパクトになりにくくなる
5. 可分になりにくくなる

M-SOLUTIONS 2020 E - M's Solution

問題

座標平面上に置かれた $n$ 個の点について，重み $P _ i$ と 座標 $(X _ i, Y _ i)$ をもつとし，点 $i$ から最も使い直線との距離を $D _ i$ とする．直線 $X = 0, Y = 0$ がある状態から始めて，各 $k = 0, \ldots, n$ について，$X$ 軸または $Y$ 軸に平行な直線を $k$ 本追加したときの $\sum _ {i} D _ i \times P _ i$ の最小値を求めよ．($n \leq 15$)

ABC 174 F - Range Set Query

問題

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

正規確率過程の Karhunen–Loève 分解

概要

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