今日の競プロ(2020/5/2) + AtCoder Beginner Contest 165

AtCoder : 1705 → 1755 (+50)

ABC165 A - We Love Golf

問題

こういうのは変に算数せず、全探索

提出

ABC165 B - 1%

問題

最大ケースがサンプルにあって優しい。C++でやったらオーバーフローしてもうたからPythonでやった。

提出

ABC165 C - Many Requirements

問題

何言ってるかよくわからないけど、とりあえず $A$ が全探索できればよさそう。 $A$ として考えられる数列は、 $M$ 個のボールと $N-1$ 個の仕切りの並べ替えと考えて ${}_{N+M-1} C_{N-1}$ 通り。これは最大でも ${}_{19} C_{9}=92,378$ なので、いける。

実装も同じように、 $M$ 個のボールと $N-1$ 個の仕切り（に見立てた $M$ 個の $0$ と $N-1$ 個の $1$ ）をstd::next_permutationで回せばいける。

提出

ABC165 D - Floor Function

問題

$x$ を $B$ で割って $x=qB+r$ とすると、

$\begin{eqnarray} \lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor &=& \lfloor \frac{A(qB+r)}{B} \rfloor - A \times \lfloor \frac{qB+r}{B} \rfloor \\ &=& (Aq+\lfloor \frac{Ar}{B} \rfloor) - (Aq + \lfloor \frac{r}{B} \rfloor) \\ &=& \lfloor \frac{Ar}{B} \rfloor -\lfloor \frac{r}{B} \rfloor \end{eqnarray}$