paizaラーニング レベルアップ問題集 線形探索メニュー応用編 JavaScript 大小関係 2

大小関係 2 (paizaランク B 相当)

解答例

問題文を正しく理解することが大事です。

以下の条件を満たす (l, r) ( l + 2 ≦ r )の組の数を答えてください。

• l + 1 ≦ i ≦ r - 1 を満たすすべての i について、
  a_{ i - 1 } < a_i > a_{ i + 1 } または、
  a_{ i - 1 } > a_i < a_{ i + 1 } である

例えば、入力例2だと
1 2 1 2 1 2 1 (入力値)
ですが、(l,r)の組がわかりやすいように番号をふると、
1 2 3 4 5 6 7 (l,rの何番目か)
です。
条件を満たす(l,r)の組と数列は、
(1,3)の1 2 1,
(1,4)の1 2 1 2,
(1,5)の1 2 1 2 1,
(1,6)の1 2 1 2 1 2,
(1,7)の1 ２ 1 2 1 2 1,
以下(l,r)の組だけ示すと、
(2,4),(2,5),(2,6),(2,7),(3,5)(3,6),(3,7),(4,6),(4,7),(5,7)で、出力値は、15個です。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

let count = 0;//条件を満たす (l, r) ( l + 2 ≦ r )の組の数
//aについて、調べる区間の左端l
for (let l = 0; l < n - 2; l++) { //( l + 2 ≦ r )なので最低三要素
　//aについて、調べる区間の右端r
  for (let r = l + 2; r < n; r++) { //( l + 2 ≦ r )なので最低三要素
    //条件を満たすか
    let flag = true;
    for (let i = l + 1; i <= r - 1; i++) {
      //満たさない
      if (!(a[i - 1] < a[i] && a[i] > a[i + 1]) &&
          !(a[i - 1] > a[i] && a[i] < a[i + 1])) {
        flag = false;
        break;
      }
    }
    //全て満たす
    if (flag) {
      count += 1;
    }
  }
    
}

console.log(count);