ABC152 C - Low Elements

備忘録

問題

atcoder.jp

私が提出した回答

"use strict"
 
function Main(s) {
  s = s.trim().split('\n');
  const n = Number(s[0]);
  const p = s[1].trim().split(' ').map(Number);
  let cnt=0;
  for(let i=1; i<=n; i++){
    let flg = true;
    for(let j=1; j<=i; j++){
      if(p[i-1] > p[j-1]){
        flg = false;
        break;
      }
    }
    if(flg)cnt++;
  }
  console.log(cnt);
}
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Submission #9620907 - AtCoder Beginner Contest 152

forの中でforを使用しているため、計算量がO(N^2)となり、
TLE（実行時間制限超過）で通りませんでした。

考え方

与えられるPは順列なので、ループを繰り返す度に最小となるPjを保持し、
Piと比較を行うだけで、条件を満たすiがカウントすることが出来た。

修正した回答

"use strict"
function Main(input) {
  const args = input.trim().split('\n');
  const n = args[0];
  const p = args[1].split(' ').map(Number);
 
  let max = 1e10; // maxよりminと命名したほうが適切だった
  let cnt = 0;
 
  for(let i=0; i<n; i++){
    if(p[i]<max) cnt++, max=p[i];
  }
 
  console.log(cnt);
}

Submission #9645642 - AtCoder Beginner Contest 152