ARC077-E - guruguru
概要
m段階の明るさを調節できるランプとリモコンがある。1回リモコンの「進む」ボタンを押すと、明るさが1段階上昇、一番上のレベルmの場合はレベル1に戻る。
もう1つ、「ショートカット」ボタンがあり、これは1回押すと、事前に決めたX段階の明るさになる。
最初に明るさはa_1になっていて、あなたはa_2, a_3, ..., a_nの順番になるように明るさを変更する。a_2に明るさをそろえて、次にa_3にそろえて、次にはa_4・・・のように。
あなたは、ショートカットのX段階へ飛ぶ機能のXを自由に決められる。自由にXを決めた時、この{a_i}のリストを達成するのに必要な最小のボタン押しの回数はいくつ？
制約: 1 <= n, m <= 10^5 1 <= a_i <= m
ACするまで
1. 愚直に解くと、xをすべて試して、そのxごとに必要な回数をO(N)かけて探索するためO(NM)でTLEする。
2. xを試すというのは削れるようには思えないため、差分で攻められるかを考える。
3. 差分を考えると、今回の場合はいくつかの条件を見事に満たすためうまくいく。->AC
考察
この問題には
- 公式解法(僕の解法でもある) O(M+N)の解法。
- 関数の重ね合わせとしてみなして、遅延セグメント木でのO(N + M log M)解法。(@hotman78 の解法)
がある。遅延セグメント木での解法は広く応用らしい。
O(M + N)の解法
この問題でのオーダーの落としどころは、
- すべてのXをM通り試す。
- 1回の試すごとにO(N)の計算量をかける。
の2つから見つけることになる。こういう時は、次のようになる。
Point
1回あたり計算量O(M)のものを、O(N)回行う愚直解の高速化は、1回あたりの計算量を差分利用(欠落してもよい情報を落としてまとめて扱うパターンが多い)などをすることで、1回あたりの計算量を改善できる場合が多い。
欠落してもよい情報を落として、まとめて扱うことによって、複雑度の次元を1つ落とすのは常套手段であり、それをこの考えと融合させたのがこの問題である。
x=pとx=p+1の時の違いを考える。
まず、ショートカットを使うと、より早くなるのは、[a_i + 1, a_(i+1)]の間にXを設定した時(この時、ショートカットの1回も入れて、1+(a_(i+1) - X + M) % M回)で、それ以外は、(a_(i+1) - a_i + M) % M回の操作となる。
このことから、x=pからp+1にした時の差分を考える。それは次の3つに大まかに分けられる。
1. p == a_i(i >= 2) つまり、ちょうどゴールにあるとき
2. a_i + 1 <= p <= a_i - 1 つまり、ゴール直下ではないが、ショートカットで短くなるとき
3. それ以外 ショートカットを使用しないほうがよいとき
1 は、p+1になると、ショートカットボタン1回で済んだのが、a_(i+1) - a_i + M) % M回必要になる。
2 は、そのような条件を満たすものすべてに対して、全部かかる操作が1回減る(ショートカットがその時のゴールに1近くなるため)。ここでは、減る量はショートカットキー利用すべきa_i -> a_(i+1)の区間(つまり、ここではiの個数)の数にのみ依存し、どの区間であるかにはよらない(つまり、どの区間でも、平等に1つであれば1手減る)。この性質によって、区間によるとしたときにかかったO(N)を個数のみで管理して、O(1)にできる！
3 は、p == a_i + 1になってるのならば、それ以降はショートカットすると楽になるため、2 の数を1つ足すでよく、それ以外はかかる手数が固定なので、特に加減する必要はない。
このように、情報を落として、個数のみで管理できるタイプの問題なので、O(NM)のうちのO(N)を落としてO(M + N)にできる。ちなみに解説では2 の部分でimos法を使ってるらしい。
O(N+M log M)の解法
この問題は、数学的にはつぎのように言い換えられる。
f(x) := xに置いたときのかかる最小の手数、としたときの整数の定義域[1, m]の中でのf(x)の最小値。
ここで、f(x)の構成方法を考えてみると、O(N + M)の考察も踏まえて、1つ1つのa_i -> a_(i+1)区間ごとに次のような結果になる。(ここでは、基本的に m -> 1へまたぐことが発生しない場合)
- [(a_i) + 1, a_(i+1)]では傾きが-1
- [a_(i+1), a_(i+1)+1]では傾きがa_(i+1) - a_i - 1
- それ以外は傾き0
のような関数を、合計N - 1個重ね合わせたのがf(x)となる。
これを実装するには、(今回定義域も小さいのもあり)、傾きを遅延セグメント木で持って、区間加算が可能になるようにするとよい。答えを計算するときは、まずO(N)かけてf(0)を計算し、セグメント木のM - 1個の区間の傾きをどんどん足していき、その最小値を見ればよい。
一言
ありがとうhotman、ありがとう世界。2つ目のテク、Convex Hull Trickに通ずるものがあって(たぶんそれより条件的に限定的にしたもの)、世の中深いところでつながってるなぁと感じる。
まとめ
Point
1回あたり計算量O(M)のものを、O(N)回行う愚直解の高速化は、1回あたりの計算量を差分利用(欠落してもよい情報を落としてまとめて扱うパターンが多い)などをすることで、1回あたりの計算量を改善できる場合が多い。
