AtCoder Beginner Contest 046

Updated:

AtCoder Beginner Contest 046

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$ 点である。

ポイント

最適戦略などない、の例。

Others