AtCoder Grand Contest 025

更新日時:

AtCoder Grand Contest 025

これもペンディング。これも D までは書く。

ソースコード

解法のメモ

A - Digits Sum

$B = N - A$ として、指定通りにするだけ。

ポイント

C++ より Ruby の方が簡単だろう。

B - RGB Coloring

赤色と青色を独立に塗っていく。両方塗られたブロックを緑色に塗ったと解釈して得点計算すればよい。

赤色を塗ったブロックの個数を $k$ 個とし、青色を塗ったブロックの個数を $l$ 個とする。すると $A k + B l = K$ が成立する。この方程式が整数解 $(k, l) \in \mathbb{Z}^2$ を持つための必要十分条件は $g = \mathrm{gcd}(k, l)$ について $g | K$ であることである。まずこれが成立していなければ答えは $0$ である。あとは $0 \leq k, l \leq N$ を充たす $(k, l)$ の解を全部求めれば良いが、これは素直に $k = 0, \dots, N$ についてループを回して求めて十分である。その解の全体集合を $S$ とおけば、求めるものは、

\[ \sum_{(k, l) \in S} \begin{pmatrix} N \\ k \end{pmatrix} \begin{pmatrix} N \\ l \end{pmatrix} \]

である。実装はすこぶる簡単である。

ポイント

数学色が強いからすぐに求めることができた。最近の高校の数学のカリキュラムには、我々の時代と違って不定方程式の整数解があるらしいから、若ければ若いほど有利である。

C - Interval Game

ポイント

D - Choosing Points

ポイント

E - Walking on a Tree

ポイント

F - Addition and Andition

ポイント

その他

コメントする