wakabame.hatenablog.com
では, の素数 で割った余りを求める方法について解説しました.
実は, この計算アルゴリズムは高速化できます.
続きを読む#include <bits/stdc++.h> using namespace std; int main() { int a; cin >> a; }
入力が小数、文字列の場合は, int の部分をそれぞれ double, string にすればよい
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M ; }
入力が小数、文字列の場合は, int の部分をそれぞれ double, string にすればよい
#include <bits/stdc++.h> using namespace std; // int N が既に与えられているとする. int main(){ vector<int> vec(N); for (int i = 0; i < N; i++) { cin >> vec.at(i); } }
C++ の標準入力においては半角空白も改行も同列に区切り文字と見なされるため, 入力が
0 1 2
であっても,
0 1 2
であっても動作に影響はない.
array を使う方法もあるが、AtCoderは初心者はvector を使うほうがいいと述べている.
https://atcoder.jp/contests/apg4b/tasks/APG4b_n
#include <bits/stdc++.h> using namespace std; int main(){ cout << A << endl; }
#include <bits/stdc++.h> using namespace std; int main(){ for(auto v: vec){ cout << v << endl; } }
#include <bits/stdc++.h> using namespace std; int main(){ for (int i = 0; i < vec.size()-1; i ++){ cout << vec.at(i) << " "; } cout << vec.back() << endl; }
問題文が迷わせに来ていますね.
全ての要素は非負ですので, りんごさんの要望を , すぬけさんの石の置き方を としたときのコスト
\begin{equation}
\sum_{i=1}^L |A_i-B_i|
\end{equation}
を最小化すればいいことがわかります.
すぬけさんの動き方はりんごさんが好きに決められるので,
を求めればよいことが分かります.
つまり,
という問題設定です.
ただし, に対する制約は結構複雑です.
すぬけさんの移動に関しては, 順番を巻き戻しても石の配置は変わらないので出発点の座標 , 終了点の座標 の間には
\begin{equation}
S\le T
\end{equation}
なる関係があるとして一般性を失いません.
そして, 出発点と終了点の間の座標に置かれている石はかならず奇数個になっています.
すぬけさんは同じ座標を行ったり来たりすることで, 任意の奇数を実現できることに注意しましょう.
これにより, が奇数ならば までコストを下げられ, 偶数ならば までコストを下げられます.
また, すぬけさんは出発点よりも左に進むことができます.
すぬけさんが訪れる左端の座標を とすると, であり, その区間に置かれている石はかならず ではない偶数個になっています.
これにより, が奇数ならば までコストを下げられ, でない偶数ならば までコストを下げられます.
であれば, この区間の最小コストは となります.
のときは, よりも左にはすぬけさんは移動していないことになるため, その区間に置かれている石は 個です.
これにより, 区間 におけるコストは そのものになります.
今までの議論は終了点の右に対しても行えます.
すぬけさんが到達できる右端の座標を とすると, これまでの議論は,
という風にまとめられます.
それぞれの区間の長さは であってもよいものとします.
例えば として,
\begin{equation}
A = [1, 0,0,0,1]
\end{equation}
であれば右端は見捨てた ] が最適(の1つ)であるのに対して,
\begin{equation}
A = [100,0,0,0,100]
\end{equation}
のような状況であれば ] とするのが最適になり,
そういったものをどう処理するかを指定するのが難しくなります.
を決定させればそのときの最小コストが求められることが分かりました.
しかしながら, それらをループで処理すると計算量は となり計算が間に合いません.
ですので, 入力の長さ に対する動的計画法(DP)を考えます.
すなわち, を任意に取るごとに, が入力であったときの最小コストを求めましょう.
というのも, に対する状態の分割が では通用しないためです.
これを確かめるために, 先ほど挙げた ] の場合を考えましょう.
今考案したDPにおいて, 入力が のときまでを考えると, が最適な配置であるのに対して,
のときは, が最良となってしまいます.
というわけで, 入力の長さ だけでなく, 現時点での右端の"戦略"を 通り保持する必要があります.
ただし, をインクリメントする際には, 右端の"戦略" よりも新しいものだけが選べることに注意します.
具体的には,
と呼ぶことにすると, 例えば状態 で考えた場合には楽で,
先頭 までの文字列のなかで, 右端の状態が のときの最小コスト
= 先頭 までの文字列のなかで, 右端の状態が のときの最小コスト
+ 文字目を状態 で実行したときのコスト
となります. さらに状態 を考える場合には,
先頭 までの文字列のなかで, 右端の状態が のときの最小コスト
= 先頭 までの文字列のなかで, 右端の状態が のときの最小コスト
+ 文字目を状態 で実行したときのコスト
となり, での状態を複数個使う必要があります.
以上のことをまとめると, 一般に, 次のような漸化式が成り立ちます.
\begin{align}
\textrm{DP}[\ell + 1][j]
&= \min_{k = 0,\cdots, j } \textrm{DP}[\ell + 1][k] + \textrm{cost}(j , A_\ell) ,\\
\textrm{cost}(j , A_\ell)
&= \begin{cases}
A_\ell &\quad \textrm{if } j =0,4,\\
A_\ell \mod 2 &\quad \textrm{if } j =1,3,\\
(A_\ell +1) \mod 2 &\quad \textrm{if } j =2
\end{cases}
\end{align}
あとはこれを実装します.
L = int(input()) A = [int(input()) for i in range(L)] DP = [[0 for i in range(5)] for j in range(L+1)] def cost(s, a): if s == 0 or s == 4: return a elif s == 1 or s == 3: if a > 0: return a%2 else: return 2 else: return (a+1)%2 for i in range(L): DP[i+1][0] = min(DP[i][:1]) + cost(0, A[i]) DP[i+1][1] = min(DP[i][:2]) + cost(1, A[i]) DP[i+1][2] = min(DP[i][:3]) + cost(2, A[i]) DP[i+1][3] = min(DP[i][:4]) + cost(3, A[i]) DP[i+1][4] = min(DP[i][:5]) + cost(4, A[i]) print(min(DP[L]))
これでめでたくACしますね
https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4228991
この記事は書きかけです.
atcoder.jp
Python で解けたものから, 自分なりに解説をつけていきたいと思います.
足場 , にたどり着くまでの最小コストを考えます.
これを と表すことにすると,
\begin{equation}
\begin{cases}
a_1 &= 0,\\
a_2 &= |h_1-h_2|,\\
a_n &= \min\{a_{n-1} + |h_n-h_{n-1}|, a_{n-2}+ |h_n-h_{n-2}| \},&\quad \textrm{if } n=3,4,\cdots, N
\end{cases}
\end{equation}
という風に一般的に表されます.
つまり, を のときもとめるには以前の計算結果を使いまわすことで結果を得られます.
を求めたいのに , をわざわざ求めるのは直観的には遠回りに感じますが,
のそれぞれの値を保存できていれば を瞬時に求めることが出来るので, うまくいきます.
N = int(input()) h = list(map(int, input().split())) DP = [0, abs(h[0]-h[1])] for i in range(N-2): DP += [min(DP[-2] + abs(h[i]-h[i+2]), DP[-1] + abs(h[i+1]-h[i+2]))] print(DP[-1])
を与えられた自然数とし, 母数 ,
, ()となるカテゴリ分布を考えます.
すなわちどれか 成分ののみが , それ以外が となるような 次元値の確率変数 に対するカテゴリ分布
\begin{equation}
\mathrm{Cat}(S|\pi) = \prod_{k=1}^K \pi_k^{S_k}
\end{equation}
を考えましょう.
本記事では, これが指数型分布族に属することを手がかりに, 共役事前分布としてディリクレ分布が得られることを示し, ついでにディリクレ分布の規格化定数を求める計算を行います.
指数型分布族の定義と, 観測モデルから決定される共役事前分布については次の記事の記法を用います:
wakabame.hatenablog.com
ディリクレ分布については, 以下の記事群が参考になります:
ディリクレ分布 - Wikipedia
ディリクレ分布の意味と正規化,平均などの計算 | 高校数学の美しい物語
規格化定数の導出については正田 備也氏の
http://www.cis.nagasaki-u.ac.jp/~masada/DirDistNorm.pdf
を参考に行いました.
あまり格好のよいことではないのだけど、内省のために書いた文章がそこそこの分量に達したし、誰かにとって有益になるかもしれないと思ったので自分語りをしてみます。軽い話ではないので、そういうのが好みではない人は読み飛ばしてください。
元々は自分向けの文章なので、表現が雑な箇所もあります。また、敬体は本文中では用いません。ご了承ください。
前回記事では行列ガンマ分布とその規格化定数の計算方法を紹介しました.
wakabame.hatenablog.com
今回はその応用として, 多次元のガンマ分布を観測モデルとするベイズ推論を行いましょう.
次の行列ガンマ分布は, パラメータである正実数 と次の対称行列 に対して
\begin{align*}
\textrm{MGam}(\Lambda|a,B)
&= C(a,B) |\Lambda|^{a-1}\exp\{-\langle B, \Lambda\rangle\},\\
C(a,B)^{-1}
&= |B|^{-(a+\frac{d-1}{2})}\pi^\frac{d(d-1)}{4}\prod_{k=1}^d \Gamma\left(a+\frac{d-k}{2}\right)
\end{align*}
と表せたのでした.