競技プログラミング用 知識集積所
ABC430C - Truck Driver
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず愚直解を考えてみる。
範囲からLとRの値を選び、その中のaとbをカウントすることで、O(N^3)で求めることはできる。
これの高速化としてまず思いつくのは累積和でaとbをカウントを高速に行うことだが、それでもO(N^2)にしかならず、必要な速度には届かない。
根本的に、「範囲からLとRの値を選び」の時点でO(N^2)は確定なので、その時点で無理である。
範囲からLとRの値を選び、その中のaとbをカウントすることで、O(N^3)で求めることはできる。
これの高速化としてまず思いつくのは累積和でaとbをカウントを高速に行うことだが、それでもO(N^2)にしかならず、必要な速度には届かない。
根本的に、「範囲からLとRの値を選び」の時点でO(N^2)は確定なので、その時点で無理である。
そこで、Rの値を固定したときに条件を満たすLの値が何個あるかを高速に求められないかと考えてみる。
（Lを固定してもいいが、ここではRを固定する方で説明をする）
Rを固定してある状態だと、Lの範囲は「遡ってaがA個以上、bがB個未満ある場所」の個数である。
aの個数やbの個数は範囲を広げると単調に増加するため、この範囲はひとつながりになっている。
よって、何らかの方法でこの区間の左端と右端を高速に求められれば、個数はその位置の差でよいことになる。
（Lを固定してもいいが、ここではRを固定する方で説明をする）
Rを固定してある状態だと、Lの範囲は「遡ってaがA個以上、bがB個未満ある場所」の個数である。
aの個数やbの個数は範囲を広げると単調に増加するため、この範囲はひとつながりになっている。
よって、何らかの方法でこの区間の左端と右端を高速に求められれば、個数はその位置の差でよいことになる。
これは尺取法のwhileで回す方の足を2つ持たせ、右端をRとする区間で「aがA個以上」「bがB個以上」になるLの範囲を求めるものとしてそれぞれを利用すればよい。
あるいは、計算量にlogNがついてしまうが、二分探索※でもこの問題なら間に合うと思われる。
あるいは、計算量にlogNがついてしまうが、二分探索※でもこの問題なら間に合うと思われる。
