Forethought Future Cup - Elimination Round: D. Frog Jumping
問題
数直線上にカエルがいる。 カエルが位置 $x$ にいるとき、位置 $x + a$ あるいは位置 $x - b$ にジャンプして移動できる。 位置 $0$ から始めて区間 $[0, x]$ の範囲内で任意回移動を繰り返して辿り着きうる座標の個数を $f(x)$ とする。 $\sum_{x \le m} f(x)$ を求めよ。
考察過程
思い出し:
- $\gcd(a, b) \ne 1$ なら割っていい感じにできる。互いに素と仮定してよい。
- $x$ が $ab$ を超えればあとは $[0, x]$ を自由に作れることになる。
- 出ている辺の数は高々 $2$ なので遅い $O(N)$ ができる。
- (解けず)
解法
D、max(A*2,B*2)までをBFSで頑張ればいいだけなんですよね
— 尺（しゃく）P (@dem08656775) 2019年4月20日
確かにA進めるなら進んで限界までB戻るを繰り返すと永遠に行けそうな気がする
— やむなく (@yamerarenaku) 2019年4月20日
$m’ = 2 \max(A, B)$ まで見てその後ろは $g(n) = \frac{n(n + 1)}{2}$ とおいて $g(m + 1) - g(m’)$ でよい。 ただし $d = \gcd(a, b) \ne 1$ のときはその考慮が必要である。 $g(n) = \sum _ {x \lt n} \left(1 + \lfloor \frac{x}{d} \rfloor \right)$ であり、 $n = qd + r$ と割って $g(n) = \left(d \sum _ {x \lt q} x \right) + (q + 1) r = d \cdot \frac{q (q + 1)}{2} + (q + 1) r$ である。
$m’$ までの部分は BFS で済むので、計算量は $O(\max(a, b))$ 。
反省
- 「自由に作れるようになるのが $ab$ から」というのが大嘘。部分的には真だが、$ab$ より手前ではだめだと思ってしまった。
- 解説見て書いて出したら $\gcd(a, b) \ne 1$ の場合を忘れてて RE した。