ABC230_E – Fraction Floor Sum
問題
提出
3回目くらいで解けた
以下、解法を書いていく。
$\lfloor \frac{N}{i} \rfloor$を$1$から$N$まで愚直に計算すると$O(N)$になってしまい間に合わない。
問題を見たときに、何していいかわからなかったので、とりあえず具体的に数値を入れて試したみた。
例えば、N=9の時、$\lfloor \frac{N}{i} \rfloor$は以下のようになる。
$$ i=1の時: \lfloor \frac{9}{1} \rfloor = 9$$
$$ i=2の時: \lfloor \frac{9}{2} \rfloor = 4$$
$$ i=3の時: \lfloor \frac{9}{3} \rfloor = 3$$
$$ i=4の時: \lfloor \frac{9}{4} \rfloor = 2$$
$$ i=5の時: \lfloor \frac{9}{5} \rfloor = 1$$
$$ i=6の時: \lfloor \frac{9}{6} \rfloor = 1$$
$$ i=7の時: \lfloor \frac{9}{7} \rfloor = 1$$
$$ i=8の時: \lfloor \frac{9}{8} \rfloor = 1$$
$$ i=9の時: \lfloor \frac{9}{9} \rfloor = 1$$
これをみると、1が連続する区間があることがわかる。
この部分はまとめて計算できそう。
この区間は$i:(4,9]$になっている。
$4$になっているのは、$4$で値が切り替わっているからである。
つまり、$\lfloor \frac{9}{2} \rfloor = 4$だからである。
よって、1が続く区間は$i: (\lfloor \frac{9}{2} \rfloor, \lfloor \frac{9}{1} \rfloor]$になる。
同様に考えて、2が続く区間は$i: (\lfloor \frac{9}{3} \rfloor, \lfloor \frac{9}{2} \rfloor]$になる。
$N=9$の時、一般に数$j$が続く区間は$i: (\lfloor \frac{9}{j+1} \rfloor, \lfloor \frac{9}{j} \rfloor]$になる。
数字の切り替わりが発生するのは、$N=9$出なくても$\lfloor \frac{N}{i} \rfloor$なので、
一般に数$j$が続く区間は$i: (\lfloor \frac{N}{j+1} \rfloor, \lfloor \frac{N}{j} \rfloor]$になる。
まとめて計算する方法がわかったが、上記を$i:1..N$まで繰り返しても$O(N)$になってしまう。
$j$が続く区間は$i: (\lfloor \frac{N}{j+1} \rfloor, \lfloor \frac{N}{j} \rfloor]$と、愚直に$\lfloor \frac{N}{i} \rfloor$を足し合わせることを合わせた方法を考える。
愚直に$i=1$から$\lfloor \frac{N}{i} \rfloor$を計算し、ある値$j$が連続して続くようになったら、$i: (\lfloor \frac{N}{j+1} \rfloor, \lfloor \frac{N}{j} \rfloor]$の区間のjを足し合わせる。
どこまでの範囲をどちらの方法で計算するかは、計算回数が小さくなるように設定したい。
方法の境界になるような値を$k$とする。
連続する値を一気に計算する方法の場合、$i: 1..k$まで計算すると考えると、$i: (\lfloor \frac{N}{k+1} \rfloor, \lfloor \frac{N}{1} \rfloor]$まで足し合わせることになる。
愚直な方法の場合、$i: 1..k$まで計算すると、$k$まで計算できる。
この方法で計算回数が小さくなる時は、両方の範囲が重なる時になるはずなので、$k = \lfloor \frac{N}{k+1} \rfloor$の時である。
大体の範囲を見積もると、$k = \frac{N}{k}$となり、$k=\sqrt N$くらいになる。
これなら$O(\sqrt N)$なので間に合う。
よって、$k=\lfloor \sqrt{N} \rfloor$とすることができる。
連続する値を一気に計算する方法の範囲を、$i: 1..k$まで計算すると考えると、$i: (\lfloor \frac{N}{k+1} \rfloor, \lfloor \frac{N}{1} \rfloor]$まで足し合わせることになる。
愚直な方法で足し合わせるのは、上記の方法でカバーできていない範囲なので、$i:[1..\lfloor \frac{N}{k+1} \rfloor]$になる。
コメント