競技プログラミング用 知識集積所
ARC208B - Sum of Mod
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
考察問題。
数列の末尾に制約があるので、後ろから作った方がやりやすい。
つまり、数列をひっくり返して広義単調減少なものを作る方がやりやすい。
以下の説明でも、逆順にした数列で説明する。
つまり、数列をひっくり返して広義単調減少なものを作る方がやりやすい。
以下の説明でも、逆順にした数列で説明する。
貪欲法※で、問題に影響しない範囲で条件を増やしていく。
まず、末尾は2以上限定で考えてよい。
なぜなら、末尾が1の場合はどこか以降が「x,1,1,……,1」(x>1)となっているはずだが、この場合はそのあたり全て余りが0なので和に一切影響を与えない。
ならばそこを「x,x,x,……,x」と変えてもいいはずだからである。
なぜなら、末尾が1の場合はどこか以降が「x,1,1,……,1」(x>1)となっているはずだが、この場合はそのあたり全て余りが0なので和に一切影響を与えない。
ならばそこを「x,x,x,……,x」と変えてもいいはずだからである。
次に、最後2つの割り算の商は1に固定してよい。
なぜなら、商が2以上で余りがrにできるならば、最後の数を大きくして商が1で余りがrにできるはずだからである。
なぜなら、商が2以上で余りがrにできるならば、最後の数を大きくして商が1で余りがrにできるはずだからである。
そして、最後から3番目と最後から2番目の割り算の商も1に固定してよい。
同様に最後から2番目を増やすことで商を1にでき、後ろも全て同じだけ増加させることで和に影響しないようにできるからである。
これを繰り返して考えると、全ての区間で商を1に固定してよい。
同様に最後から2番目を増やすことで商を1にでき、後ろも全て同じだけ増加させることで和に影響しないようにできるからである。
これを繰り返して考えると、全ての区間で商を1に固定してよい。
すると、剰余は単に引き算になるため、問題にある総和は、単に「初項-末項」を計算すればよくなる。
ということは、途中の値も「1つ前の半分より大きければ、広義単調減少である限りなんでもいい」ということになる。
そこで、途中の値も「1つ前の半分より大きいなかで最小の整数（ただし次項を下回らない）」に決めてしまってよい。
ということは、途中の値も「1つ前の半分より大きければ、広義単調減少である限りなんでもいい」ということになる。
そこで、途中の値も「1つ前の半分より大きいなかで最小の整数（ただし次項を下回らない）」に決めてしまってよい。
以上で、初項と末項を決めれば途中の数列が一意に決まることになった。
さらに言えば、前しか見ずに数列を作っていくことで、初項に対して最小の末項が容易にわかる（つまり和の最大値が容易にわかる）ということになる。
さらに言えば、前しか見ずに数列を作っていくことで、初項に対して最小の末項が容易にわかる（つまり和の最大値が容易にわかる）ということになる。
問題は「和がKになる最大の初項（元の問題では末項だが）」を求める指示なので、初項を1ずつ増やしながら和がK以上にできるか判定すればいい。
末項が2以上として考えているので、調査は初項がK+2の場合からスタートすればよい。
末項が2以上として考えているので、調査は初項がK+2の場合からスタートすればよい。
ただし、ここまでだとまだTLEする。
それは、Kが莫大で項数が極小の場合、例えばK=10^9でNが2の場合、最小の初項が2*10^9+1になるので、ループが10^9近く回るからである。
そこで、以下のように考える。
それは、Kが莫大で項数が極小の場合、例えばK=10^9でNが2の場合、最小の初項が2*10^9+1になるので、ループが10^9近く回るからである。
そこで、以下のように考える。
初項を1増やしたとき、末項が減ることはない。
言い換えれば、初項を1増やして和が2以上一気に増えることはない。
つまり、ある初項で計算して和の最大値がKまで100足りない場合は、次の初項の調査は一気に+100して調べてよい。
この方針だと、調査回数が悪くてもO(logK)で収まるので、十分高速に終わる。
言い換えれば、初項を1増やして和が2以上一気に増えることはない。
つまり、ある初項で計算して和の最大値がKまで100足りない場合は、次の初項の調査は一気に+100して調べてよい。
この方針だと、調査回数が悪くてもO(logK)で収まるので、十分高速に終わる。
以上で答えるべき数列の逆順ができたので、元の順に戻すか、後ろから出力すればよい。
