アルゴリズム

AGC044 の A 問題「Pay to Win」を Python で解いてみる

再帰を書くのが苦手です. 問題はこちら: atcoder.jp 問題概要 次の選択肢を繰り返すことで初期値 を にするための最小コストを求めよ. コスト を払うことで, 数値を 倍する コスト を払うことで, 数値を 倍する コスト を払うことで, 数値を 倍する コスト …

「割った余り」での割り算は、既約分数にしなくても答えは変わらない

この記事では, を素数とし, の下での割り算について述べます. 整数 に対する の下での割り算 では, 分数 が既約分数になっていなくても計算結果は変わりません. そのことを述べていきます. 復習 wakabame.hatenablog.com でも触れましたが, まずは逆元とは何…

Python で mod の下での逆元を計算するテーブルを作成する

wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます.

みんなのプロコン2019 D-Ears をPython で解いてみる

問題文が迷わせに来ていますね. 全ての要素は非負ですので, りんごさんの要望を , すぬけさんの石の置き方を としたときのコスト \begin{equation} \sum_{i=1}^L |A_i-B_i| \end{equation} を最小化すればいいことがわかります. すぬけさんの動き方はりんご…

ABC088 を Julia で解いてみる

先ほどまで開催されていた AtCoder の ABC088 に参加してみました。 問題や解説についてはリンク先をご覧ください。 abc088.contest.atcoder.jp 最近は数値計算をしてみたいなと思うところがあり、Julia の勉強を始めていました。 というわけで、使い慣れて…

フェルマーの小定理を使って mod の下での組み合わせ総数を求めるアルゴリズムを python で書いてみる

注意:この記事は未完成です。こちらの記事を参考にお願いします wakabame.hatenablog.com の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,と表されます. 階乗…

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

整数 と整数 に対して, を整数 で割った余りを出力します. 安直に を 回乗じてからで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります. 回乗じるのに計算量が かかってしまう. は処理しきれなくなるくらい大きくなりえる. この…

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

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

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

動的計画法(DP)について, qiita でまとめられました qiita.com 勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は として書きます. ここで, は数列の要素数を表します. 1. 最大和…

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

有向グラフとは 有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は の形式を持ち, 頂点 から頂点 へはコスト で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません. 今回…

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

グラフの一種である木構造での距離を求めるアルゴリズムを考えます. グラフとは 詳しくは グラフ理論 - Wikipedia などの記述をご参照ください. グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを…

最長増加部分列の長さ取得アルゴリズムLISをpythonで書いてみる

最長増加部分列(Longest Increasing Subsequence )とは 数列 が与えられたとき, その部分列 であって のとき を満たすものを増加部分列と言います. その中で最も長いものの長さを求めるアルゴリズムを以下に説明していきます.