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

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

新規登録して質問してみよう
ただいま回答率
85.37%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

3回答

804閲覧

Atcoder beginner contest でTLEが出る

Henjin213

総合スコア22

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2021/06/20 10:03

編集2021/06/20 12:56

以下のコードでTLEが出ます。プログラミング初心者で実行速度等わからずにやっていますが、そんなに複雑な処理をしていないように思いますが、対処法を教えて頂きたいです。

python

1N = int(input()) 2lis = list(input().split(" ")) 3 4total = 0 5for a in range(N): 6 for b in lis[a:]: 7 if lis[a] != b: 8 total += 1 9 10print(total)

問題文:https://atcoder.jp/contests/abc206/tasks/abc206_c

よろしくおねがいします。

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

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

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

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

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

BeatStar

2021/06/20 10:33

ご自分の質問を第三者的視点で読んでみましょう。 どういう問題なのか分かりますか? プログラムは書いた通りにしか動きません。 ソースコードだけ見せられてもわかりませんよ。 例えば「入力されるデータの個数が多すぎるため」とかのようなソースコード以外の部分が問題だったりする。 それをソースコードだけ見せられてもわかりません。 回答者は質問者と同じ環境にある……わけではありません。 回答者は提示された情報からしか理解できません。
Henjin213

2021/06/20 12:55

申し訳ありません!!問題のリンクを張ったつもりで忘れてました!!
guest

回答3

0

今回のNの制約は最大で3 * 10 5です。テストケースの中にlen(lis)が本当にその長さのものがあったとき、ご提示のコードでは a = 0 で lis[0] <= b <= lis[N - 1], a = 1 でlis[1] <= b <= lis[N - 1], ...となりループによる計算の数だけで(N * (N + 1) // 2) 回 >> 10 8となり、定数倍計算による処理時間も考慮するとこれはTLEとなって当然でしょう。

対処法を、と言う話ですが、これがAtCoderはじめ競技プログラミングの本質です。上のような考え方は最初から競プロのどの世界でも「完全にダメな答案」の扱いであり、これをどのようにいじる云々の問題ではなく、アルゴリズムの世界では何をどの場面でどのように活用するかが試されます(今回であれば、例えば配列をソートしてみたらどのような見やすさが生じるか、さらに配列のソートによって問題の答えにどう影響が出るか、そこからどのようにして多重ループを減らすか、など)。ただそうは言っても、最初はC問題レベルの内容だとそんなんわかるわけないと思われると思うので、まずは数多とある過去問に取り組んでください。初歩的なアルゴリズムの学習では、最低限のパターンと言うのはやはり高が知れているので、それらを網羅できるように思考法と知識を整理するように取り組んでください。少なくともこちらで質問されるのでしたら、そういった計算量を意識したコーディングを出来るようになってからが良いかと思われます(その頃には回答者視点でも答えやすい内容の質問になっていると考えられますので)。

投稿2021/06/20 12:40

編集2021/06/20 12:42
kay_ventris4

総合スコア269

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

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

Henjin213

2021/06/20 12:58

丁寧な回答ありがとうございます! 競技プログラミングがどいういうものかわかっていなかったので、とても参考になりました。
guest

0

  • そんなに複雑な処理をしていないように思いますが、

一般的に言って、高速なアルゴリズムはそうでないアルゴリズムよりも複雑です。
つまり、「そんなに複雑な処理をしていない」ということは遅いアルゴリズムで実行しているということです。
その結果、制限時間オーバーが出ているのでしょう。

  • 対処法を教えて頂きたいです。

もう少し複雑で、もう少し高速なアルゴリズムを考えましょう。

ヒント: lisの中の順番を変えてもtotalは同じになります。

投稿2021/06/20 12:49

ppaul

総合スコア24668

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

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

0

コード自体はシンプルでも、N が大きいときループする回数が多くなるためです。
N が最大のときも実行時間制限以内に処理できる計算量のプログラムを組む必要があります。

投稿2021/06/20 11:12

yh1224

総合スコア653

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

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

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

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

ただいまの回答率
85.37%

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

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

質問する

関連した質問