AGC005 B Minimum Sum

Minimum Sum

Submission #3330734 - AtCoder Grand Contest 005 | AtCoder

問題概要

要素数Nの順列が与えられる。すべての区間の最小値の和を求めよ。

取った方針

N=200000なので、すべての区間を列挙すると間に合わない。a_iが最小値になる区間の個数を数えてそれにa_iをかけたものの和を求めればよい気がするが、a_iが最小値になる区間の個数を数えられず終了

正しい方針(解説の方針)

a_iが小さい順に区間の個数を数えることを考える。
それまでに見た数(1,2,...a_i-1)の位置を記録しておくと、a_iが最小値になりうる区間の左端はインデックスがi以下で最大のもの、右端はi以上でインデックスが最小のものとなる。
これは、1,2...a_iまでのインデックスをsetに入れておき、a_iの一つ前/一つ後を取得することで得ることができる。
なぜなら、上記のようにすると、a_i以下の数のインデックスのみsetに入ることになるからである。

得られた知見

• どう考えても全列挙は不可能(区間)->全列挙可能なもの(区間の個数)に着目
• 条件A(a_iより小さい)を満たす中でB(インデックスがiより大きい/小さい)なもの->条件Aをみたす集合の中で考えると見通しがよくなることがある
  • 例 : a_iよりも小さい数のうちインデックスがi以下で最大のもの　はa_i以下の数のインデックスのsortedなsetの中ではiの隣に来る

解くのに必要な要素

• 厳しい制約->厳しくない部分に着目
• 小さい方/大きい方から確定させていく
• 条件を満たすものの集合内で考える

周辺調査によって得られた知見

なし