もくじ

• 問題リンク
• はじめに
• 結果
• C - Triangular Relationship
  • 問題
  • 考察と解法
• D - All Your Paths are Different Lengths
  • 問題
  • 考察
• 感想

問題リンク

Tasks - AtCoder Regular Contest 102

はじめに

結果

今回は1完で594位だった。

1完を目的としていたので、それは達成できて良かった。

あと2分速く解けていれば水色パフォだった……

C - Triangular Relationship

問題

問題リンク →　

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

考察

頂点数が 10⁶ であるから2²⁰ が関連していそうなことは見通しがついた。

ただし、実際にグラフを作ってみると、この解法だと頂点数が21無ければならず、辺の数が足りないことに気づく。

さらに、大きい方の重みから作っていけば辺の数を減らしていくことができそうだが、明らかに足りないことにも気づく。

ここでARC終了。

感想

1完できて良かったが、Cはもう少し速く解ければ良かったかな……

Dもただ重みをつけるだけでなく、重みのつけかたを工夫する必要があった。

逆に言えばもう少しでACできそうだったので、次こそDを解きたい。