ARC004_C - rydotの呟''

ケアレスミス記念＆はてダ記念。

僕の解法(?)はこんなのだった。

1からNまでの平均値= $\frac{N+1}{2}$

足し忘れ数M= $\frac{(N+1)N}{2} - N\frac{X}{Y}$

$0 < M \leq N, \: M \in \mathcal{N}$ となるNを見つける。

このままではNの範囲がわからないので不等式を変形して範囲を求める。

下限

$0 < \frac{N}{2} + (\frac{1}{2} - \frac{X}{Y})$

$2\frac{X}{Y} - 1 < N$

上限

$\frac{N}{2} + (\frac{1}{2} - \frac{X}{Y}) \leq N$

$N \leq 2\frac{X}{Y} + 1$

というわけで下限と上限が求まった。
よくみると範囲はめちゃくちゃ狭い。
ところが下限の計算をミスって $O(\frac{X}{Y})$ の線形探索になってしまい、どこで計算を削ろうかと考えてしまいタイムアップだった。もったいない。