アルゴリズムロジック

ユークリッドの互除法とその拡張

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。 このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズム...

2019/12/06 21:02

二項係数(nCk)を素数で割った余りの計算

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7...

2019/12/04 17:03

【AtCoder Beginner Contest 145】C – Average Length

問題 元の問題: C - Average Length N個の全ての点を1回ずつ通るような動き方は\(N!\)通りある。総移動距離の平均を求めよ。 解き方 順列を使って解く方法 ...

2019/12/03 14:47

順列(n!)の全探索

順列の全探索とは \(n!\)通りの全探索を行いたい時に順列が用いられます。 順列(permutation)とは、n個のものを順番に並べるのは何通りあるかを考える問題です。n個全...

2019/12/02 16:00