AtCoder Beginner Contest 198のきろく - Flkanjin’s 競プロ録

A - Div (100点)
B - Palindrome with leading zeros (200点)
C - Compass Walking (300点)
D - Send More Money (400点、実行時間制限: 5 sec)
E - Unique Color (500点)
F - Cube (600点): 未提出
結果、感想

A - Div (100点)

A君が $x$ 個貰うとすると、B君は $N-x$ 個貰うことになるので $1 \leq x \leq N$ かつ $1 \leq N-x \leq N$ より $N \geq 2$ のとき $1 \leq x \leq N-1$ より $x$ は整数であるため $N-1$ 通り存在します。 $N=1$ のとき条件を満たす分け方は存在しないので、どちらの場合も $N - 1$ 通りとなります。

B - Palindrome with leading zeros (200点)

$N = 0$ でない限り先頭に0はもともと来ないので末尾の0を削除した文字列が回文なら条件を満たし、そうでなければ条件を満たしません。
文字列が条件を満たしているかどうかは実際に両端から文字が等しいかどうか調べることで判別できます。

C - Compass Walking (300点)

$1$ 歩移動後に高橋くんがいる点の集合は半径 $R$ の円周となります。
そのあともう $1$ 歩移動することで、

$R\begin{pmatrix} \cos\alpha \\ \sin\alpha \\ \end{pmatrix} + R\begin{pmatrix} \cos\beta \\ \sin\beta \\ \end{pmatrix} = \displaystyle 2R \cos\frac{\alpha-\beta}{2} \begin{pmatrix} \cos\dfrac{\alpha+\beta}{2} \\ \sin\dfrac{\alpha+\beta}{2}\\ \end{pmatrix}$

となり、 $\alpha+\beta$ と $\alpha-\beta$ の組は $\mathbb{R}^2$ の全域を動くことができるため点の集合は半径 $2R$ の円周及び内部になります。
これ以降は、数学的帰納法により、 $i\,(\geq 2)$ 歩移動後の点の集合は半径 $iR$ の円周及び内部となります。
よって、原点から $(X,\,Y)$ の距離が $R$ の時は答え $1$ 、 $R$ 未満の時は答え $2$ 、それ以外の時は答え $\displaystyle \left\lceil \frac{距離}{R} \right\rceil$ となります。
誤差が怖かったのでfor文を用いて条件を求めましたが、繰り返し回数を $100\,000$ 回にしていたため、1つのケースを落としてしまい、2ペナとなってしまいました。上限は $R = 1,$ $(X,\,Y) = (100\,000,\,100\,000)$ のときの $141\,422$ となります。

D - Send More Money (400点、実行時間制限: 5 sec)

最初、覆面算 $S_1 + S_2 = S_3$ という条件を見落としていて1ペナついてしまいました(問題名の意味を考えれば...)。
文字と数字が対応するため $11$ 種類以上の文字を用いている場合、UNSOLVABLEとなります。
そうでない場合、文字と数字の対応を全て試してみます。高々 $10! = 3\,828\,800$ 通りなので間に合います。std::next_permutaionを用います。 $1$ 文字目が0でないか、stollを用いて $N_1 + N_2 = N_3$ が成り立っているかどうかを判別しましょう。