プログラミング雑記:dwango2015

・じぶんが書いたやつ
Atcoder上に提出した自分のコードがたどれないっぽいので、あとで見返せるようにリンクをまとめておく必要がある気がする。
dwango2015A:http://dwango2015-prelims.contest.atcoder.jp/submissions/322837
dwango2015B:http://dwango2015-prelims.contest.atcoder.jp/submissions/324624
dwango2015B:http://dwango2015-prelims.contest.atcoder.jp/submissions/325636
dwango2015C:http://dwango2015-prelims.contest.atcoder.jp/submissions/326034

・C - ゲーマーじゃんけん
　無限級数の和を式にするまでが勝負、
　E(n) = (1 + (勝つ人がいるときのそれ以降の期待値の総和)) / (1 - (あいこになる確率))
でいいはず。
公式解答はここ：「dwangoプログラミングコンテスト」予選問題解説 / SSSSLIDE
まず状態遷移からの期待値は
$\displaystyle E(n) = \sum_{k=1}^{n}{ \left\{ E(k)+1 \right\} P(n,k)}$
で、sumのnの部分を取り出すと
$\displaystyle E(n) = \left\{ E(n)+1 \right\} P(n,n) + \sum_{k=1}^{n-1}{ \left\{ E(k)+1 \right\} P(n,k)}$
$E(n)$ を移項して整理して、
$\displaystyle E(n) = \frac{P(n,n) + \sum_{k=1}^{n-1}{ \left\{ E(k)+1 \right\} P(n,k)}}{1-P(n,n)}$
$\sum_{k=1}^{n-1}$ から足す1を取り出して、 $P(n,1)$ から $P(n,n)$ までまとめると
$\displaystyle E(n) = \frac{1 + \sum_{k=1}^{n-1}{E(k)P(n,k)}}{1-P(n,n)}$
ここで $P(n,n)$ が「あいこになる確率」、 $\sum_{k=1}^{n-1}{E(k)P(n,k)}$ が「勝ちが出たときのそれ以降のラウンド数の期待値」になる。あとは全パターンを回してそれが出る確率を「あいこ」と「あいこにならない」もので振り分けるようなループを書けば良い感じ。公式解答見るまでうんぬん悩んでて馬鹿っぽかった。離散確率は状態遷移考えて式書いたら余裕だよね～わからなかったらノードの取り方を変えてみればいいよね～。

・doubleの出力精度指定

  #include <iomanip>
  ...
　cout << setprecision(16) << d << endl;

のようにする。setprecisionは出力する小数点以下の桁数の指定。
iomanipをincludeすれば使える。細かいことはiomanipのリファレンス見ればわかる。
http://www.cplusplus.com/reference/iomanip/

・Combination
　算数を忘れた。

double cmb[n][n] = {};
for (int i = 0; i < n; i++) {
	cmb[i][0] = 1;
	for (int j = 1; j <= i; j++) {
		cmb[i][j] = cmb[i-1][j-1] + cmb[i-1][j];
	}
}