AtCoder Beginner Contest 190をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 190を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Very Very Primitive Game

愚直に条件を確認します. 基本的にはアメの個数が多い人の勝ちで, アメの個数が同じ場合にはどちらが先手かによって変わります.

各魔法に対して, ダメージを与えられる条件を満たしているかを順に確かめていきます.

$1 \leq K \leq 16$であり, ボールが置かれる場合の数(重複あり)は$2 \leq 2^K \leq 65536$であるので, ボールが置かれる場合を全探索しても問題ないでしょう.

各ボールの置き方に対して, そのボールの置き方で各条件を満たすことができるかを確認し, 結果条件を満たすことができた個数を数えます. その最大値を出力すればよいです.

初項$A$, 末項$B$($A \leq B$), 公差$1$の等差数列の和は,

\begin{align} N &= \frac{\left( A + B \right) \left( B - A + 1 \right)}{2} \end{align}

です. よって, この問題は,

\begin{align} \left( A + B \right) \left( B - A + 1 \right) &= 2N \end{align}

の整数解$A$, $B$を求める問題になります.

$A + B$, $B - A + 1$はともに自然数になります^*1ので, どちらも$2N$の正の約数になります. $2N$を正の約数$x$, $y$に分解できたとして,

\begin{align} \left\{ \begin{aligned} & A + B = x \\ & B - A + 1 = y \end{aligned} \right. \end{align}

を$A$, $B$について解くと,

\begin{align} \left\{ \begin{aligned} & A = \frac{x - y + 1}{2} \\ & B = \frac{x + y - 1}{2} \end{aligned} \right. \end{align}

となります. もし, $x$と$y$の偶奇が同じなら, $A$, $B$は整数になりません. したがって, $x$と$y$の偶奇は異なる必要があります. よって, この問題は, $2N$を偶奇の異なる2つの自然数$x$, $y$に分解する問題になります.

また, $2N$は$2$を必ず素因数に含みますが, その$2$という素因数は$x$と$y$のどちらか一方にしか含まれることができません. 仮に,

と, $y$として当てはまるのは$d_1$, $d_2$, $d_3$, $d_4$のみです^*3. $x$と$y$が入れ替わった場合も考えると, 求める値は$M$の約数の$2$倍になります.

E以降は私の能力不足故に省略いたします.

*1 : $A$と$B$がどちらも自然数である場合, これは明らかです. また, $A$と$B$がどちらも自然数ではないとすると, 等差数列の和が自然数にならないのであり得ません. $B$だけが自然数だとすると, 以下のようになります.

したがって, $A + B$, $B - A + 1$はともに自然数になります.

*2 : もちろん何個だとしても問題ないです.

*3 : $x$には各$y$に対して適切な値が当てはまります.