アルゴリズム
再帰を書くのが苦手です. 問題はこちら： atcoder.jp 問題概要 次の選択肢を繰り返すことで初期値 を にするための最小コストを求めよ. コスト を払うことで, 数値を 倍する コスト を払うことで, 数値を 倍する コスト を払うことで, 数値を 倍する コスト …
この記事では, を素数とし, の下での割り算について述べます. 整数 に対する の下での割り算 では, 分数 が既約分数になっていなくても計算結果は変わりません. そのことを述べていきます. 復習 wakabame.hatenablog.com でも触れましたが, まずは逆元とは何…
wakabame.hatenablog.com では, の素数 で割った余りを求める方法について解説しました. 実は, この計算アルゴリズムは高速化できます.
問題文が迷わせに来ていますね. 全ての要素は非負ですので, りんごさんの要望を , すぬけさんの石の置き方を としたときのコスト \begin{equation} \sum_{i=1}^L |A_i-B_i| \end{equation} を最小化すればいいことがわかります. すぬけさんの動き方はりんご…
先ほどまで開催されていた AtCoder の ABC088 に参加してみました。 問題や解説についてはリンク先をご覧ください。 abc088.contest.atcoder.jp 最近は数値計算をしてみたいなと思うところがあり、Julia の勉強を始めていました。 というわけで、使い慣れて…
注意：この記事は未完成です。こちらの記事を参考にお願いします wakabame.hatenablog.com の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,と表されます. 階乗…
整数 と整数 に対して, を整数 で割った余りを出力します. 安直に を 回乗じてからで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります. 回乗じるのに計算量が かかってしまう. は処理しきれなくなるくらい大きくなりえる. この…
ワーシャル＝フロイド法とは 今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマ…
動的計画法(DP)について, qiita でまとめられました qiita.com 勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は として書きます. ここで, は数列の要素数を表します. 1. 最大和…
有向グラフとは 有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は の形式を持ち, 頂点 から頂点 へはコスト で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません. 今回…
グラフの一種である木構造での距離を求めるアルゴリズムを考えます. グラフとは 詳しくは グラフ理論 - Wikipedia などの記述をご参照ください. グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを…
最長増加部分列(Longest Increasing Subsequence )とは 数列 が与えられたとき, その部分列 であって のとき を満たすものを増加部分列と言います. その中で最も長いものの長さを求めるアルゴリズムを以下に説明していきます.
