Atcoder 競技プログラミングの鉄則 演習問題集 第5問のREになってしまう理由がわからないです。

Question

実現したいこと

ソートコードの原因解説と私のコードをどのように修正すればよろしいでしょうか？

発生している問題・分からないこと

私のコードでコンパイル提出するとREになってしまいます。

該当のソースコード

N,K = map(int, input().split())
count = 0

for i in range(1, N+1):
    for j in range(1, N+1):
        for z in range(1, N+1):
            if i+j+z == K:
                count += 1

print(count)

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

特に変更したりAIは使ってません。

補足

特になし

Comments

[melian]

入力例2の場合、ループ回数は 3000**3 = 27,000,000,000 回(270億回)になります。手元のPC(Intel Core i5-8500T (6)/3.50 GHz)で実行すると10分経過しても終了しません。つまり、制限時間オーバーになっていると考えられます。なので、修正方法としては総当り(brute force)ではなく適切なアルゴリズムを採用することになります。

[TakaiY]

僕も時間がかかることが問題かと思ったのですが、その場合REでなくTLEになるんじゃないかと思って黙ってましたがどうなんでしょう。

[melian]

三重ループを二重ループにするとループ回数は900万回になります。先程の環境では1.77秒で完了なので間に合うかもしれません。もっと効率的な方法があるかと思いますが、参考にしてみてください。
https://www.mycompiler.io/view/598zz3iL7CF

[bsdfan]

時間がかかりすぎているのならREではなくTLEになると思います。
ひとつ前の質問でも、正常に動作する回答のものでREになったりしているようなので、コピペでのミスとか、その辺も注意してみたほうがいいように思います。
pythonの場合、インデントでのエラーもREになると思います。

[kikukiku]

こんな感じにすると計算量が更に半分にできそう。
https://www.mycompiler.io/view/E4Nl6x3p9Vz

[meg_]

> Atcoder 競技プログラミングの鉄則　演習問題集 第5問のREになってしまう理由がわからないです。
URLは追記できますか？

> 特に変更したりAIは使ってません。
何の話ですか？「試したこと・調べたこと」を記入する欄なのでプログラムの補足情報は本文に書く情報かと思います。

[actorbug]

REになると言っているのは、こちらの提出結果のことでしょうか。
https://atcoder.jp/contests/tessoku-book/submissions/69378422
こちらですが、Atcoder 競技プログラミングの鉄則　演習問題集 第5問ではなく、第1問に対して回答しています。
第5問に回答したいのであれば、こちらのページにソースコードを入力してください。
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_e

[kikukiku]

>こんな感じにすると計算量が更に半分にできそう。
>https://www.mycompiler.io/view/E4Nl6x3p9Vz
上記では計算量を半分にできないことが判明しました。
すみません。取り下げます。

[TMYchan]

@actorbugさん
解答ありがとうございます。以下のリンクで再度提出しましたら、結果がTLEになりました。
しかし、上のコードだとなぜ時間がかかりすぎてしまうのですがなぜでしょうか。

[TakaiY]

> 結果がTLEになりました。
> しかし、上のコードだとなぜ時間がかかりすぎてしまうのですがなぜでしょうか。

この問題って、「1 章：アルゴリズムと計算量」の題名にもありますが、パッと思いつく方法だと計算量が多くて時間がかかりすぎてしまう問題を、適切なアルゴリズムを1つまたは複数適用することで制限時間内に解けるようになること、が目的の演習問題です。
なので、アルゴリズムや計算量の見積り方などを勉強してこの問題が解けるようになりましょう。って感じですね。

[kikukiku]

TMYchanさんのアルゴリズムは、
Nの３重ループになっているので、
最大3000×3000×3000＝270億回ループすることになります。
アルゴリズムを工夫することで
Nの２重ループにすることができます。
3000×3000＝900万回
上記にようにすれば、3000倍処理速度を上げることができるということですね。

２重ループへの仕方は、すでに他の方が回答している通りです。

Answer 1

質問へのコメントにも書かれていますが，提示されたコードでは実行時間の条件を満たせないと思われますので，少し視点を変えた方法を示します。

1枚目のカードが i（1 〜 N）の場合，残り（j = K - i）に着目すると以下のことが言えます。

• j が2枚目と3枚目のカードの和の範囲（2 〜 N + N）外の場合は条件を満たさないのでカウントは不要

• j が N + 1 以下の場合は，2枚目も3枚目も 1 以上が条件なので2枚目と3枚目の和が j に一致する場合の数は j - 1 通り

• j が N + 1 を超える場合は，3枚目が N 以下なので2枚目は j - N 以上の必要があり，求める場合の数は N - (j - N - 1) 通り

これらを基にした記述例を下記に示します。

また，AtCoder への 提出結果 も参照ください。

N, K = map(int, input().split())
count = 0

for i in range(1, N + 1):
    j = K - i
    if j < 2:
        continue
    elif j <= N + 1:
        count += j - 1
    elif j <= N + N:
        count += N + N - j + 1

print(count)

Comments

[kikukiku]

実行時間制限が２秒なんですね。
ちゃんと問題文を読んでいなかったです。
２秒なら１重ループにおさめておかないと無理ですね。
すばらしい。