読者です 読者をやめる 読者になる 読者になる

足跡-sokuseki-

りかの日進月歩の記録

AGC005 B Minimum Sum

昨日解いていて、解説を見ても理解するのに手こずったので、考え方を書いてみる(一応この問題について書いてるブログはあったけど、解法が違ったので、自分用に)。

B: Minimum Sum - AtCoder Grand Contest 005 | AtCoder


問題概要


 1 から  N までの数字を並べ替えた長さ  N の数列  a_1, a_2, … , a_N が与えられるので
 \sum_{l=1}^{N} \sum_{r=l}^{N} min(a_{l}, a_{l+1}, … , a_{r}) を求める。

つまり、長さ  N の数列の  _N C _2 個の区間それぞれについて最小値を求め、それの合計を求める。

制約は  N <= 2 \times 10^5 のため、計算量は高々  O(N)  O(N log N)


TLE解法


自力で思いついたのは全区間の最小値を順番に足していく  O(N^2) の解法。
調べる区間の幅をだんだん大きくしていくという考え方。

Submission #1101992 - AtCoder Grand Contest 005 | AtCoder

ansの初期値に代入している  \frac{n(n+1)}{2} は、隣り合う1項の最小値(つまりその項自身)の合計値。数列には  1 から  N までの数がそれぞれ1回ずつ出てきているので、等差数列の和と考えて計算する。

repの中では、隣り合う  N-i+1 項の最小値を計算してansに足していく。

区間(部分数列)でいうと
{ a_0, a_1 } { a_1 , a_2 } … { a_{N-2} , a_{N-1} }
{ a_0 , a_1 , a_ 2 } { a_1 , a_2 , a_3 } … { a_{N-3} , a_{N-2} , a_{N-1} }

{ a_0 , … , a_{N-2} } { a_1 , … , a_{N-1} }
{ a_0 , … , a_{N-1} }
の最小値を順番に求めている。

setを使った解法


 O(N log N) の解法は「最小値が  a_i となる区間がいくつあるかを計算し、その区間数と  a_i の積の合計を求める」。

 a_i が最小値となる区間は、数列の  a_i より前の部分で  a_i に一番近いところにある  a_i よりも小さな値との距離、数列の  a_i より後ろの部分で  a_i に一番近いところにある  a_i よりも小さな値との距離がわかれば求めることができる。


たとえば、{5, 4, 9, 2, 1, 8, 6, 7, 3}という数列の6が最小値となる区間を考える。
6が最小値になる区間は6より小さな値が存在しないので、もとの数列の6より小さい値にだけ色をつけると
{5, 4, 9, 2, 1, 8, 6, 7, 3}
となり、6より小さな値(赤色の数字)が存在しないような区間(部分数列)は{8,6}{8,6,7}{6}{6,7}の4つとなる。
ここで、6が最小値となる区間の左端は、はじめの数列の「6より左にあって6より小さな一番6に近い値(=1)」よりも右で、6よりも右ではない数字になっていることがわかるので、6が最小値となる区間の左端は8,6のどちらかであり、この8,6という左端の候補の数(=2)は「6より左にあって6より小さな一番6に近い値(=1)」と6との距離である。
同様に、6が最小値となる区間の右端は6,7のどちらかであり、右端の候補の数(=2)は「6より右にあって一番6に近い6より小さな値(=3)」と6との距離である。
そして、6が最小値となる区間の数は(左端の候補の数)*(右端の候補の数)より2*2=4個と求めることができる。

今見ている数字  a_i が最小値となる区間の数を求めるためには、 a_i の左右それぞれで、 a_i より小さく  a_i に一番近い数との距離が必要になる。 よって、要素を自動的にsortしてくれるsetに、 a_i より小さな値の添字を入れておき、 a_i の添字iに一番近い数をlower_boundを使って高速に調べればよい。

 a_i が最小値となる区間を調べる際に必要な情報は「  a_i よりも小さな値がどこにあるのか」なので、できるだけ小さな  a_i 、つまり1から順番に調べていくと、区間数を調べた後にsetに a_i をそのまま入れることができるので、効率よく求めることができる。

setの要素の挿入に  O(logN) 、set内のlower_boundに  O(logN) かかるので、 a_i それぞれに対して行っても  O(N log N )



Submission #1102173 - AtCoder Grand Contest 005 | AtCoder

入力を配列aで受け取り、配列orderには、区間数を調べる  a_i の順番になるように、 a_i の添字iを格納する。つまり、a[order[0]]=1, a[order[1]]=2, … , a[order[N-1]]=Nとなるように格納する。

はじめにsetに入れた-1とNは番兵の役割をする。 a_i の前に  a_i より小さな値が存在しないときは-1が返され、 a_i の後ろに  a_i より小さな値が存在しないときはNが返される。

あとは最小値が1となる区間、最小値が2となる区間、…と順番に区間の数を計算してtmpに入れて、ansに足していく。



その他の解法


pekempeyさんがUnion-Findを使った解法を解説しています。

AtCoder Grand Contest 005: B. Minimum Sum - pekempeyのブログ


また、standingsで他の人のソースコードを見てみると、stackを使った解法などもあるようです(私にはよくわからなかったのですが……)。


最後に


この問題が400点なんて嘘ですよね?(500はありそうだと思った)