2013-10-08

問題

N( $\leq 5\times 10^5$ )人の名前と値が与えられる。初めにK番目の人(1から始まる)からスタートし、選ばれた人は抜ける。抜ける際に、p番目の人はpの約数だけ飴がもらえる。次の人は、その人の値分だけ時計回りした番号の人になる。マイナスの場合は逆回転となる。飴の最大数とその名前を求めよ。

解法

Binary Indexed Tree(BIT)、二分探索、エラトステネスの篩っぽい約数の個数を求める前処理で解ける。約数の数を求める前処理はkomiyamさんの記事を参考にした。他の箇所もいくつか参考にしたので、同じようなコードになっている。
BITを用いることで、途中で人が抜けた場合でも次の順番の人を計算することができる。初めに、0~Nまでに+1をする。その後、抜けていく番号の部分に-1をする。こうすることで、 $logN$ で次の人が計算可能になる。
例を用いて説明する。6人いるとする。この時のBITの各要素は以下となる。
$1 2 3 4 5 6$
その後、2番目と5番目の人が抜けたとする。
$1 1 2 3 3 4$
こうすることで、抜けた人の分を考慮したインデックスをsumを用いることで求めることができる。抜けた人の分を考慮したインデックスから本当のインデックスを求めるには、二分探索を用いれば良い。

約数の個数を前処理

約数の個数はナイーブに実装すると、ある値の約数の個数を求める場合の計算量は $O(N)$ なので、 $O(N^N)$ となる。このアルゴリズムを用いると、大雑把に見積もって $O(N)$ となる。しかし、これは少なく見積もっている。
アルゴリズムの大まかな原理を説明する。
合成数2700を考える。2700は以下の素因数を持っている。
2,2,3,3,3,5,5
この素因数を用いた積の組み合わせの合計が約数の個数となる。素因数を用いているので積が同じになることはない。
2の時のパターンは
1 2 4
3の時のパターンは
1 3 9 27
5の時のパターンは
1 5 25
となり、これを計算すると3*4*3となり36となる。