AtCoder Beginner Contest 046
Updated:
Source codes
Solutions
A - AtCoDeerくんとペンキ / AtCoDeer and Paint Cans
set<int> S; に突っ込んで S.size() を出力する。
B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer
左端を塗るのに $K$ 通り、以降他のマスを塗るのに $K - 1$ 通り。よって答えは $K(K-1)^{N - 1}$ 通りである。
ポイント
意外と時間かかった。
C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report
高橋君の直前の得票数を $X$ 票、青木君の直前の得票数を $Y$ 票とする。この時点で $T:A$ の情報が出たとすると、 $N \in \mathbb{N}$ が存在し $X \leq NT$ かつ $Y \leq NA$ を充たす。このうち最小の $N$ を選ぶべきであるから、 $N = \max((X + T - 1)/T, (Y + A - 1)/A)$ である。ここで割り算は計算機の割り算。あとは $X \gets NT$, $Y \gets NA$ とするのを繰り返す。
ポイント
小数に直して WA をもらった。よくない。整数でやるべきだった。
D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper
$P = \sharp\{ 0 \leq i < N \mid s[i] = p \}$ とする。相手の全ての手に $g$ を出す場合、得点は $-P$ 点である。仮にある手を $p$ に変更すると、相手の手が $g$ だった場合はあいこから勝ちになるので $+1$ 点される。相手の手が $p$ だった場合は負けからあいこになるので $+1$ 点される。どちらも同じである。つまり出来るだけ $p$ を出すようにするのが最善の戦略である。そこで $gpgpgp \dots gp$ と出していく。得点は $N/2 - P$ 点である。
ポイント
最適戦略などない、の例。