ARC102 - 参加記録
問題リンク
Tasks - AtCoder Regular Contest 102
はじめに
結果
今回は1完で594位だった。
1完を目的としていたので、それは達成できて良かった。
あと2分速く解けていれば水色パフォだった……
C - Triangular Relationship
問題
問題リンク →
考察と解法
が全て
の倍数であることから、
%
=
%
=
%
= 0 - (1)
がわかる。
さらに、を固定すると、
%
= 0 より
%
=
%
. - (2)
%
= 0 より
% K
=
%
. - (3)
(1), (2), (3)より、
%
=
%
%
) = 0
を満たしていればが全て
の倍数であることを満たす。
そして、(2),(3)を満たすようなb, cは余りが %
となるものなので、その個数はそれぞれ
である。
最後に、を
から
まで回すと答えが導出できる。
以下、提出コード。
Submission #3116072 - AtCoder Regular Contest 102
D - All Your Paths are Different Lengths
問題
問題リンク →
D - All Your Paths are Different Lengths
考察
頂点数が 106 であるから220 が関連していそうなことは見通しがついた。
ただし、実際にグラフを作ってみると、この解法だと頂点数が21無ければならず、辺の数が足りないことに気づく。
さらに、大きい方の重みから作っていけば辺の数を減らしていくことができそうだが、明らかに足りないことにも気づく。
ここでARC終了。
感想
1完できて良かったが、Cはもう少し速く解ければ良かったかな……
Dもただ重みをつけるだけでなく、重みのつけかたを工夫する必要があった。
逆に言えばもう少しでACできそうだったので、次こそDを解きたい。
