Codeforces Round #338 (Div. 2): 1690 → 1815

2回目のCF参加。当面は1900を目標にしています。

codeforces.com

公式解説: Codeforces Round #338 (Div. 2) editorial - Codeforces

A. Bulbs

やるだけ。魔が差してRubyを使った。 $O( N M )$

Submission #15238098 - Codeforces

0:03:10

B. Longtail Hedgehog

英語がつらい。なぜか幅優先やってる人が多かった。 $O( N + M )$

Submission #15242011 - Codeforces

解法はあっていたがオーバーフローされた。最悪。次から#define int long long人間になってやる

正しいの: Submission #15267183 - Codeforces

0:20:06

C. Running Track

貪欲に最長の切り取りを繰り返す。3重ループだけど $O( N ^ 2 )$

Submission #15244268 - Codeforces

0:38:44

$\prod p_i^{c_i} ( \forall i \neq j, p_i \neq p_j )$ の形にする。 $C_* = \prod( c_i + 1 )$ とすると、答えを素因数分解したときの各素数の指数は、 $\dfrac{C_*}{c_i + 1} \dfrac{c_i ( c_i + 1 )}{2} = \dfrac{C_* c_i}{2}$ となる*1。あとは繰り返し二乗法で答えを求めるだけ。
剰余について、 $C_*$ は指数になるので、フェルマーの小定理より $MOD - 1$ を用いる。今回は最後に2で割るため、あまりは $2 ( MOD - 1 )$ でとっておく。 $O( M \log M )$

Submission #15248011 - Codeforces

1:09:23

E. Hexagons

簡単すぎてこわかった。難しさが見つからない。
現在の周回数 $l$ は $n = 3 l \left( l + 1 \right) = 3 \left( \left( l + \dfrac{1}{2} \right) ^ 2 - \dfrac{1}{4} \right)$ となるので $l = \left\lceil \sqrt{\dfrac{n}{3} + \dfrac{1}{4}} - \dfrac{1}{2} \right\rceil$ という式で求められる。 $O( 1 )$