blog.bouzuya.net

2022-01-28 第八回 アルゴリズム実技検定 (PAST) N - ジグザグな数列 を解いた

第八回 アルゴリズム実技検定 (PAST) N - ジグザグな数列 を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_n

意外と自力で解けた。

数字の大小関係が <><... か ><>... となるような「ジグザグな数列」がいくつ含まれるかを求める。

まず N <= 2 * 10^5 なので部分列すべてを調べることはできない。何かしらの工夫が必要だ。

入力例 1 で考える。

3
1 3 2
  • 1 の時点では < も > も 0 だ
  • 1 3 の時点では 1 < 3 で < が 1 で > は 0 だ
  • 1 3 2 の時点では
    • 1 < 2 で < が 1
    • 3 > 2 で > が 1
    • 1 < 3 > 2 で > が 1
  • 合計すると 4 個

1 < 3 > 2 については 1 < 3 のものを再利用すれば良さそうだ。

  • < はそこより左側に A_i よりも小さいものについてその箇所での > の数 + 1 だ
  • > はそこより左側に A_i よりも大きいものについてその箇所での < の数 + 1 だ

そこより左側というのは左から順に走査しながら状態を変更していけば自然とそうなる。

A_i より小さいものの個数は BIT やセグメント木で求められる。 A_i の出現数を保持しておき、 0..A_i の範囲の和を取れば良い。一点加算区間和なので BIT にした。

「 A_i よりも小さいものについてその箇所での > の数」を個別に求めるのは難しい。ただ必要なのは総和なので出現数の代わりに > を保持しておけば良い。 > の側も同様だ。

つまり BIT で出現数・その時点での A_i に対する > の個数・その時点での A_i に対する < の個数をそれぞれ持っておけば良い。

最後は BIT で保持している > および < の総和を求めると答えになる。

まだ問題がある。 A_i <= 10^9 になっている。この問題において A_i の値自体には意味はなく大小関係だけが重要なので座標圧縮すれば良い。一度 BTreeSet で A_i をまとめて、昇順に位置を値として振り直す。これを C とする。 0 <= C_i < N になる。

10^9+7 で mod を取ることを忘れないように。

解説とはすこし違っていた。

腹痛がする。

今日のコミット。