1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-04-10

はじめに

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

コード

当時の考察

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)になる。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?