Atcoder beginner contest でTLEが出る

Question

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

N = int(input())
lis = list(input().split(" "))
 
total = 0
for a in range(N):
    for b in lis[a:]:
        if lis[a] != b:
            total += 1
 
print(total)

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

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

Comments

[BeatStar]

ご自分の質問を第三者的視点で読んでみましょう。

どういう問題なのか分かりますか?

プログラムは書いた通りにしか動きません。

ソースコードだけ見せられてもわかりませんよ。

例えば「入力されるデータの個数が多すぎるため」とかのようなソースコード以外の部分が問題だったりする。

それをソースコードだけ見せられてもわかりません。

回答者は質問者と同じ環境にある……わけではありません。

回答者は提示された情報からしか理解できません。

[actorbug]

どの問題かを質問に書いておかないと、誰も答えられませんよ。
コードからすると、AtCoder Beginner Contest 206 の C - Swappable でしょうか。
https://atcoder.jp/contests/abc206/tasks/abc206_c

[Henjin213]

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

Answer 1

今回の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問題レベルの内容だとそんなんわかるわけないと思われると思うので、まずは数多とある過去問に取り組んでください。初歩的なアルゴリズムの学習では、最低限のパターンと言うのはやはり高が知れているので、それらを網羅できるように思考法と知識を整理するように取り組んでください。少なくともこちらで質問されるのでしたら、そういった計算量を意識したコーディングを出来るようになってからが良いかと思われます（その頃には回答者視点でも答えやすい内容の質問になっていると考えられますので）。

Comments

[Henjin213]

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

Answer 2

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

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

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

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

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

Answer 3

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