xxxasdfghjk999のブログ

iroiro

ARC 102 C - Triangular Relationship

問題

C - Triangular Relationship

解法

コンテスト中は, ひたすら $a$ を固定して $b,c$ の数を数える方法を探していた.
まず, 問題文を式に表してみると,
$a + b = n_1K$
$b + c = n_2K$
$c + a = n_3K$
$a$ を固定してみたときとりあえず $b,c$ は
$b = n_1K-a$
$c = n_3K-a$
表すことができる. また,
$b + c = n_1K-a + n_3K-a$ より
$2a = n_1K-n_2K + n_3K$ が成り立ちます.
また, 条件から各 $a,b,c$ について
$1 \leq a,b,c \leq N$ より
$b$ について
$1 \leq n_1K - a \leq N$
が成り立ち, $c$ についても対称性から同じものが成り立ちます. これを変形すると, $n_1$ について
$\frac{a+1}{K} \leq n_1 \leq \frac{N+a}{K}$
となり, $n_3$ についても
$\frac{a+1}{K} \leq n_3 \leq \frac{N+a}{K}$
が成り立つ必要があります.
いま, $a$ を固定しているため, 不等式から $n_1$ と $n_3$ が取りうる値の数を求め, 掛けあわせれば場合の数を求めることができます(同じ式の形なので, 片方を求めて二乗すればよい).
しかし, 式
$b = n_1K-a$
$c = n_3K-a$
は $a$ を固定することにより得ているので正しいが,
$2a = n_1K-n_2K + n_3K = (n_1-n_2+n_3)K$
は, $a$ と $K$ の値によっては成り立たない場合があります.
$2a$ が $K$ の倍数でないときはこの式を満たすことはできません. 逆に, $2a$ が $K$ の倍数のときは, 両辺を $K$ で割り, $n_2$ を導出することができるため, $2a$ が $K$ で割り切れることは, この式を満たす必要十分条件となっています.
よってその場合のみ数を数えないことにします.
これを $1 \leq a \leq N$ について行い, すべての場合の数を足しこむと答えが得られます.

提出

Submission #3118170 - AtCoder Regular Contest 102

感想

早ときしたかったが, 頭が足りなかった. 想定解法ではさらに踏み込んだ数学をして数えるものを単純化している. Twitterでも想定解法の人が多く, 自分がみている限り, この解き方をしている人は少なかった. 想定解法では $O(1)$ だが, 自分の解法では $O(N)$ かかる. 制約がもう少し厳しければ想定解法に近づけたかもしれないが, 負け惜しみである.