AtCoder Beginner Contest 109 - seriruの技術屋ブログ

AtCoder Beginner Contest 109に参加しました。結果はA,B,Cの3完でした。

解けたところまで解説します。

A ABC333

AとBの積が偶数ならば、次にどんな数をかけても奇数にはなりません。
よって、

A * Bが奇数 -> Yes, A * Bが偶数 -> No

と分岐させれば良いです。

sample code:

与えられる文字列がしりとりのルールに従っているか判定する問題です。

様々な実装が考えられますが一番単純なのは、

だと思います。

2の検査を行う際に文字列をstringで管理すると、back()とfront()で比較ができるので実装が少しわかりやすくなると思います。

sample code:

始点Xから始めて数直線上の都市(点)全てに訪れたいとき、1回の最大移動距離はいくつになるかという問題です。

この問題で大事なのは、点を通過するのではなく、全ての点で止まる必要があるということです。

そのため、全ての点は始点から $D \times n$ ( $n$ は自然数 )の距離に存在しなくてはいけません。

$x_i = D \times n_i$ であるので、 $D$ は $x_i$ の公約数であることがわかります。

以上より、求めるのは $x_1 - D, x_2 - D \cdots x_n - D$ の最小公約数になります。

最小公約数はユークリッドの互除法で簡単に求めることができます。

sample code:

(code内のgcdは greatest common divisor (最小公約数) の略です。)