小さい素数modの二項係数

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

Google Code Jam 2021 Qualification Round

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

AOJ DPL_2_B 中国人郵便配達問題

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

ABC 187 F - Close Group

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

ABC 187 E - Through Path

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

ABC 186 F - Rook on Grid

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

ARC 110 C - Exoswap

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

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 を使う．