はてぶで数式を書く
動的計画法のアレを書いてて数式がはてぶで書けたらいいなと思ったらどうやらTexが書けるようで
k's diary様のサイトを参考にしました↓
TeXで数式をはてなブログに表示する - k's diary
で数式の表示
DP\left\[k\right\]\left\[n\right\] = \displaystyle\sum_{(s∈S)} (DP\left\[k-1\right\]\left\[n\right\] \times DP\left\[k-1\right\]\left\[s\right\] \times EloRate(n,s))
>自分のターンのとき\\ dp\left\[left\right\]\left\[right\right\] = max\{dp\left\[left\right\]\left\[right-1\right\] + b\left\[B-right+1\right\] ,dp\left\[left-1\right\]\left\[right\right\] + a\left\[A-left+1\right\]\} (left \neq 0 \land right \neq 0 のとき)\\ dp\left\[left\right\]\left\[right\right\] = dp\left\[left\right\]\left\[right-1\right\] + b\left\[B-right+1\right\] (left = 0のとき)\\ dp\left\[left\right\]\left\[right\right\] = dp\left\[left-1\right\]\left\[right\right\] + a\left\[A-left+1\right\] (right = 0のとき)\\ >相手のターンのとき\\ dp\left\[left\right\]\left\[right\right\] = min\{dp\left\[left\right\]\left\[right-1\right\],dp\left\[left-1\right\]\left\[right\right\] \}(left \neq 0 \land right \neq 0 のとき)\\ dp\left\[left\right\]\left\[right\right\] = dp\left\[left\right\]\left\[right-1\right\](left = 0のとき)\\ dp\left\[left\right\]\left\[right\right\] = dp\left\[left-1\right\]\left\[right\right\](right = 0のとき)\\
配列の括弧の表示が面倒ですね...
AtCoder-Typical DP Contest C問題をやりました
C問題もやりました。
以下問題文
C: トーナメント - Typical DP Contest | AtCoder
Problem Statement
2K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。
第 1 ラウンドでは、1 と 2、3 と 4、… が試合を行う。
第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), … が試合を行う。
第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), … が試合を行う。
以下同様に第 K ラウンドまで行う。
第 K ラウンドの終了後に優勝者が決定する。人 i の Elo Rating が Ri であるとき、人 i の優勝確率を求めよ。
ただし、Elo Rating RP の人 P と Elo Rating RQ の人 Q が対戦した場合、人 P が勝つ確率は 1⁄(1+10(RQ−RP)⁄400) であり、異なる試合の勝敗は独立であるとする。
Constraints
1≤K≤10
0≤Ri≤4000
Input Format
入力は以下の形式で標準入力から与えられる。
K
R1
…
R2K
Output Format
答えを 2K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10−6 以下のとき正当と判定される。
書いたソースは続きから↓
続きを読む