質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
標準入力

標準入力(stdin)は、プログラムが標準的に用いるデータ入力元。リダイレクトしない限り、プログラムを起動した端末のキーボードが標準入力になります。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

デバッグ

デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Q&A

2回答

1052閲覧

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

Kota.Y

総合スコア25

標準入力

標準入力(stdin)は、プログラムが標準的に用いるデータ入力元。リダイレクトしない限り、プログラムを起動した端末のキーボードが標準入力になります。UNIX系OSやC言語に実装されて普及した概念ですが、他のOSや言語も含めた総称としても使われます。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

デバッグ

デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

0グッド

0クリップ

投稿2020/06/14 13:41

編集2020/06/14 13:57

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

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

問題

イメージ説明

コード

javascript

1function Main(input) { 2 input = input.split("\n"); 3 let itenum = parseInt(input[0]); 4 let str = input[1].split(" "); 5 let array = []; 6 for (let i = 0; i < itenum; i++) { 7 array.push(parseInt(str[i])) 8 } 9 let count = 0; 10 for (let ite = 0; ite < itenum; ite++) { 11 let isDivisible = false; 12 for (let t = 0; t < itenum; t++) { 13 if (t == ite) continue; 14 if (array[ite] % array[t] == 0) { 15 isDivisible = true; 16 break; 17 } 18 } 19 if (!isDivisible) count++; 20 } 21 console.log(count); 22} 23Main(require("fs").readFileSync("/dev/stdin", "utf8"));

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2020/06/14 13:53

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

回答2

0

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

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

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

投稿2020/06/14 13:54

miyabi_takatsuk

総合スコア9528

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

anndonut

2020/06/27 13:20

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

0

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

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

js

1 for (let ite = 0; ite < itenum; ite++) { 2 let isDivisible = false; 3 for (let t = 0; t < itenum; t++) { 4 if (t == ite) continue; 5 if (array[ite] % array[t] == 0) { 6 isDivisible = true; 7 break; 8 } 9 } 10 if (!isDivisible) count++; 11 }

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

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

投稿2020/06/22 15:37

maai

総合スコア463

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問