Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Good Bye 2019 - B. Interesting Subarray

codeforces.com

概要

次の問題をt回解け。
長さnの数列aが与えられる。それの空でない連続部分列のうち、(最大値)-(最小値)>=(連続部分列の長さ)になってるのならば、aはよい数列とする。例えば[1, 1, 4, 5, 1, 4]は[1, 4, 5, 1]は5-1>=4を満たすので、[1, 1, 4, 5, 1, 4]はよい数列である。
良い数列ならば、"YES"と答え、その条件を満たす部分列[l, r]のlとrを出力、よくないのならば"NO"と答えよ。

制約: 1 <= t <= 10^4, 2 <= n <= 2 * 10^5, 全ケースのnの合計は2 * 10^5を超えない, 0 <= a_i <= 10^9

ACするまで

1. 部分列の長さによって基準が変動するので、セグ木などで殴れないタイプ
2. どうすればいいんだ。。。。コンテスト終了



3. こういう、部分列の長さに依存する条件から、考察すると、条件の言い換えをしてみる。
4. 条件の言い換えをするとすごく簡単だとわかる。->AC

考察

部分列の長さが条件の時、僕が見た限りだと次のような方法がある。
1. 連続部分列の和ならば、対象数列aをa_i += iすることで、ここから累積和を取る。求める際の引き算で、数列の長さによってフレキシブルな部分はこれで対処できる。(どこかのAtcoderコンテストで例題がある)
2. そうでない場合は、条件の言い換えを行う。両隣などの小さいユニットに分解したときの条件を考えてみる。

今回は後者である。
任意の連続部分列というのが条件なので、ひとまず適当に小さいサイズで考えてみる。
サイズ1では、どうあがいても無理。
サイズ2では、小さい方をs、大きい方をbとすると、b-s>=2を満たす必要がある。
サイズ3では、小さい方から、s, t, bとすると、b-s>=3...

さて、構築問題にもあるように、小さいものを組み合わせて大きいものをつくる精神でサイズ3以上を考えてみる。
サイズk(k >= 3)の時、サイズ2の条件はサイズkの時の十分条件であると示す。
サイズkの時、サイズ2の条件を何一つ満たさないとすると、各項で |a_{i+1}-a_i|<=1となる。これを0, 1, 2, ..., k-1まで足し合わせると Xになるとすると、
 X<=k-1となる。ここで、 Xは実際のサイズkの最大値と最小値の差以上であるので、(等号成立条件は今見てる連続部分列が単調性を持つとき。それ以外は三角不等式により、これ以下になる)
よって、k以上になりえないので、必ずサイズ2で成り立つものを少なくとも1つ包含するとわかる。

実戦ではここまで厳密な証明はしなくてよいが、三角不等式的なノリで、小さいときに条件を満たせば、大きいときにも必ず条件を満たしそうと推測できると強い。連続部分列の条件は、細分化して考えてみる、ということが念頭にあればこの問題は解ける。

ここまで考えると、隣り合わせたもので差が2以上のものが見つかれば、それを出力し、そうでなければ存在しないとすればよい。

ACソースコード
Submission #68032021 - Codeforces

一言

こんな簡単なことにも気づかなかったなんてー(カーチャマボイス)