IndiaHacks 2016 - Online Edition C. Bear and Up-Down

codeforces.com

問題概要

数列 a が与えられる。a[i] と a[j] を入れ替えた数列がジグザグ(増加→減少→増加→減少→…)になるような i,j の選び方は何通りあるだろうか。

数列 a はジグザグでないことが保証されている。

解法

数列 a はジグザグでないため、a[i] は必ずジグザグでない部分になる。

ジグザグでない部分が 10 箇所もあると一回のスワップでジグザグにすることはできないので、選び方は 0 通りである。

ジグザグでない部分が 10 箇所未満であれば、a[i] の選び方はたかだか 10 通り、a[j] の選び方はたかだか 150000 通りなので、全部試しても間に合う。

スワップした後にジグザグになっているかどうかを判定するときは、スワップした要素の周辺ととジグザグでない部分の周辺を何個か見るだけでいい。

IndiaHacks 2016 - Online Edition C. Bear and Up-Do ...

方針を間違えると泥沼にはまりそうな問題。