AGC017 B. Moderate Differences

問題

N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。
いま、空白のマスに、以下の条件を満たすように数字を入れることができる。

• 隣接するどの2マスについてもその差はC以上D以下

このとき、条件を満たすように数字を入れることができるかどうか判定せよ。

制約

3 <= N <= 5*10^5
0 <= A,B <= 10^9
0 <= C <= D <= 10^9
変数はすべて整数

解法

Aの右隣の空白に何を入れられるか考える。
条件から、減らす方向に[A-D,A-C]と増やす方向に[A+C,A+D]の範囲の数字を入れることができる。
続けて、その隣には、ひとつ前の範囲[x,y]に対して、[x-D,y+D]の範囲が該当する。
最終的に、Bのマスまで来たとき、範囲にBが含まれているものが存在すればYESと答えられる。
しかし、この方法では、マスを進めるにつれ、範囲の数が2倍になっていくので、指数関数的に大きくなっていってしまう。

また、各マスで範囲が重なるような部分をマージするような方法をとったとしても、C==Dの時を考えればわかるように、範囲の数が多くなり、計算量が線形ではなくなるのでTLEしてしまう。

ここで気づきたいのは、各マスでは、「減らす方向への範囲更新」と「増やす方向への範囲更新」の2つの変化をさせられるが、これを行う順番はマスの位置に依存せず、それぞれを何回行ったか？だけでBのマスでの範囲が決まる。

増やす方向の回数をX回、減らす方向の回数をY回とすると、Y=N-1-Xとなる。
このとき、Bマスでの範囲は、[A+X*C-Y*D,A+X*D-Y*C]になる。
Xは、0回～N-1回まで考えられるが、それはループを回せばよいので、範囲内にBが入るかどうかを試せば、O(N)で求められる。

反省

変なコード書いてメモリ使い切ってPC再起動とかやらかしてしまっていた。
(さらに強制終了したせいでPC調子悪くなってダメ)
ちゃんと、計算量的使用メモリ的に問題ないアルゴリズムを考えてから書き始めること。