mod の下での指数計算をするアルゴリズムを python で書いてみる

python アルゴリズム 整数

整数 a と整数 n に対して, a^n を整数p で割った余りを出力します. 安直に a を n 回乗じてからpで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります.

  1. n 回乗じるのに計算量が O(n) かかってしまう.
  2. a^n は処理しきれなくなるくらい大きくなりえる.

この2点を解消する方法について解説します.

続きを読む

重み付き有向グラフの全2点間の距離を求める Warshall–Floyd 法を python で書いてみる

アルゴリズム python グラフ

ワーシャル＝フロイド法とは

今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマン＝フォード法は以前紹介しました:
wakabame.hatenablog.com

今回紹介するワーシャル＝フロイド法では, 頂点の集合を V としたとき, 任意の頂点 i,j に対してその間の最短距離を一挙に計算してしまいます. その代わり, 計算量は O(|V|^3) とやや大量になってしまいます.

続きを読む

典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる

アルゴリズム python 動的計画法DP

動的計画法(DP)について, qiita でまとめられました

qiita.com
勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は a[0], a[1],\cdots ,a[N-1] として書きます. ここで, N は数列の要素数を表します.

1. 最大和問題

N要素を持つ数列 a[0], a[1],\cdots ,a[N-1] から任意の個数の項を選んで和を取った時の最大値

def max_sum(N, a):
    dp = [0] * (N + 1)
    for i in range(N):
        dp[i + 1] = max(dp[i], dp[i] + a[i])
    return dp[N]
続きを読む

有向グラフ上の2点間の最短距離を求めるアルゴリズム Bellman–Ford 法を python で書いてみる

python アルゴリズム グラフ

有向グラフとは

有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 へはコスト c で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません.
今回はグラフの情報と始点が与えられたとき, 各頂点への最短距離をベルマン＝フォード法と呼ばれるアルゴリズムで求めていきます.
また, 有向グラフ上の2点間の最短距離を求めるアルゴリズムにはダイクストラ(Dijkstra)法と呼ばれるものもありますが, ベルマン＝フォード法の強みは辺の重みは負でもよいことが挙げられます.
一方, 負の重みを持つ辺があるときに考えなくてはならないのは負閉路の検出です. 閉路を一周するごとに距離をマイナスにすることができるものが存在する場合, その閉路を何度も通ることで最短距離をいくらでも縮めることができてしまい, 最短経路が定まりません. ですので負閉路が存在(かつ始点から到達)する場合には最短距離の代わりに警告を返します.

続きを読む

ABC070 の D 問題を python で解いてみる

ABC-D python 競技プログラミング AtCoder グラフ

木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます.

問題はこちら
abc070.contest.atcoder.jp

続きを読む

重み付き木構造上の2点間の距離を求めるアルゴリズムを python で書いてみる

python アルゴリズム グラフ

グラフの一種である木構造での距離を求めるアルゴリズムを考えます.

グラフとは

詳しくは グラフ理論 - Wikipedia などの記述をご参照ください.
グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを表しているものです（頂点の集合は自然数の部分集合と同型なので, それぞれの頂点には何番目の頂点かを表す自然数が割り当てられます. 一般には辺それぞれには実数の重みがあり, その頂点同士の移動にかかるコストを表しています. 辺は (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 はコスト c で隣接していることを表しています. 重み付きでない場合は, c=1 と理解します.
辺に向きがあるもの（つまり, 2つの頂点について行けるのに戻れなかったりコストが等しくなかったりするもの）を有向グラフ(directed graph), 辺に向きがないもの（つまり, 頂点間のコストは行きと帰りで等しいもの）を無向グラフ(undirected graph)といいます. 無向グラフでは (v_1, v_2, c) なる辺があったとき, 逆向きの (v_2, v_1, c) を辺にもつ有向グラフと解釈することもできます.

続きを読む