プログラミング雑記: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];
	}
}