[ABC247 E] Max Min ざっくり解説

はじめに

公式ともちょっと違う上、シンプルそうなので書く。例によって数学的な証明とか言われてもわからない。

コード

当時の考察

N<10**5なので、O(N)かO(NlogN)の解法になりそう。

該当の範囲は下記4つの条件を満たしているはず。

1. Xを含む範囲
2. Yを含む範囲
3. Xより大きい数を含まない範囲
4. Yより小さい数を含まない範囲

ちょっと条件が多くてややこしい。Xより大きい数またはYより小さい数を跨ぐような範囲はあり得ないので、そういう数字は数列の区切り文字みたいな感覚で飛ばし、分割された各々の数列に対しての範囲を考えていく。こうすれば1,2のみの条件を考えればよい。

さて、対象の数列を走査して、条件を満たす範囲の数を考えてみる。

条件から、該当範囲にはXとYが含まれている。としたとき、左から4番目にXがでたあと、8番目にYの両方がでてきたとき、

???X???Y
 ??X???Y
  ?X???Y
   X???Y

という感じになる。ということは、この時点で4つのパターンが満たしていることが言える。すなわち、左端からXが出てくる番号までの個数分パターンが増える、ということになる。

さて、次に来る数字について、場合分けして考えてみよう。

Xではない場合

???X???Y?
 ??X???Y?
  ?X???Y?
   X???Y?

この場合でも引き続き4番目にあるXまでは左の数字を削れるので、4つのパターンを数え上げればよい。

Xの場合

???X???YX
 ??X???YX
  ?X???YX
   X???YX
    ???YX
     ??YX
      ?YX
       YX

先ほどと比べてYのある8番目まで削れるので、8つのパターンを数え上げればいい。

従い、走査している添え字までの間で最も右に来るXとYの位置を保存しておいて、どちらか小さいほうのパターン数を数え上げることができる。
あとは、冒頭に書いたX以上or以下の数字が来た時だけリセットすればよい。

計算量は線形走査するだけなのでO(N)になる。