【JavaScript】AtCoderでTLEになる理由がわからない

Question

AtCoderで提出したコードがコード自体はあっているのに時間超過でACになりません。

どこが原因なのでしょうか。

問題

コード

function Main(input) {
  input = input.split("\n");
  let itenum = parseInt(input[0]);
  let str = input[1].split(" ");
  let array = [];
  for (let i = 0; i < itenum; i++) {
    array.push(parseInt(str[i]))
  }
  let count = 0;
  for (let ite = 0; ite < itenum; ite++) {
    let isDivisible = false;
    for (let t = 0; t < itenum; t++) {
      if (t == ite) continue;
      if (array[ite] % array[t] == 0) {
        isDivisible = true;
        break;
      }
    }
    if (!isDivisible) count++;
  }
  console.log(count);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Comments

[swordone]

まず、問題は何でしょうか。

Answer 1

AtCoderは、
処理にかかる時間も含めて、問題、ですので、そこを考えるのが質問者さんへ与えられた課題です。

同じ結果をえるためにいくつもの方法があり、短時間で終えれる書き方もあれば、膨大な時間をかけてしまう書き方もあります。
その解消をするために、アルゴリズムを一生懸命考えるわけです。

強いて回答するなら、
forで総当たりしているのが最大の原因かと。
組み合わせ爆発といって、膨大な計算量が必要になる書き方になってしまっているのでしょう。
総当たりにならない書き方を考えていかれるといいかと思います。

Comments

[anndonut]

強者相手の問題の解法がほいほい回答としてあがってくるわけはないですよねー

Answer 2

書かれているコードが時間超過することを示します。

まず、数列Aが全て異なる素数とします。制約から、これは可能です。
次に、以下の部分を見ます。

  for (let ite = 0; ite < itenum; ite++) {
    let isDivisible = false;
    for (let t = 0; t < itenum; t++) {
      if (t == ite) continue;
      if (array[ite] % array[t] == 0) {
        isDivisible = true;
        break;
      }
    }
    if (!isDivisible) count++;
  }

外側のループは、itenum回実行されます。
内側のループは、if (array[ite] % array[t] == 0) を無視すれば、ite回実行されます。
しかし、if (array[ite] % array[t] == 0) を無視しなくてもite回実行される可能性があります。
数列Aが全て異なる素数を仮定しているので、このif文は必ずfalseになるからです。

よって、この部分のコードは、外側のループと、内側のループ合わせて時間計算量 O(N*N) になります。
入力制約では最大 N = 200000 との事なので、この時間計算量では2秒には間に合わないでしょう。