「 RGB Triplets」 atcoder ABC162 計算量に関するお伺い

標題の問題は以下です。
https://atcoder.jp/contests/abc162/tasks/abc162_d
お伺いしたい点は３点です。

①以下のコードをpython3.8.2で提出するとTLEとなり、pypy7.3.0で提出するとACになります。言語仕様といえばそれまでですが、具体的にどこが高速化されているのかお伺いしたいです。

python
1N = int(input())
2S = input()
3a = S.count('R')*S.count('G')*S.count('B')
4    
5for i in range(N-2):
6    for j in range(i+1,N-1):#②の質問箇所
7        if S[i]!=S[j]:
8            if j+j-i<=N-1: #③の質問箇所
9                k = j+j-i
10                if S[j]!=S[k] and S[i]!=S[k]:
11                    a -= 1
12print(a)

②他の方の回答例を見るとjの上限をN-1からi+(N-i-1)//2+1に変えると範囲がさらに絞れてACになるのですが、このように上限を限定できる理由をお伺いしたいです。

python
1N = int(input())
2S = input()
3a = S.count('R')*S.count('G')*S.count('B')
4    
5for i in range(N-2):
6    for j in range(i+1,i+(N-i-1)//2+1):#①からの改変箇所
7        if S[i]!=S[j]:
8            if j+j-i<=N-1:
9                
10                k = j+j-i
11                if S[j]!=S[k] and S[i]!=S[k]:
12                    a -= 1
13print(a)

③質問①の条件式を一部変えて、以下コードにするとpythonでもACになります。
if文の条件を満たさないために以降が実行されず次のループに行くケースと、breakによって次のループに行くケースの計算量は一般的に後者の方が速いのでしょうか。具体的になぜ速くなっているかをお伺いしたいです。

python
1N = int(input())
2S = input()
3a = S.count('R')*S.count('G')*S.count('B')
4    
5for i in range(N-2):
6    for j in range(i+1,N-1):
7        if S[i]!=S[j]:
8            if j+j-i>=N:#③の質問箇所
9                break
10            k = j+j-i
11            if S[j]!=S[k] and S[i]!=S[k]:
12                a -= 1
13print(a)

初心者質問で恐縮ですが、計算量にお詳しい方、以上３点のご回答よろしくお願いいたします。

episteme

2020/12/15 10:04

Pythonコードでtabが消えてるのは致命的。 Markdownで書き直してください。

jbpb0

2020/12/15 10:15

pythonのコードの一番最初の行のすぐ上に ```python だけの行を追加してくださいまた、pythonのコードの一番最後の行のすぐ下に ``` だけの行を追加してください

sysy21

2020/12/15 11:49

コード部分を読みやすいように修正を行いましたので、ぜひ質問のご回答をよろしくお願いいたします。

sysy21

2020/12/16 10:13

コード部分を読みやすいように修正を行いましたので、ぜひ質問のご回答をよろしくお願いいたします。

jbpb0

2020/12/16 10:58 編集

https://qiita.com/OKCH3COOH/items/f0c5c4681bc30dddf7f4 を見ると、pythonのforループはpypyよりも20倍くらい時間がかかってますループの中に代入を一つだけ入れると、さらに遅くなり35倍くらい時間がかかってます 35倍は20倍の2倍に近いわけで、forループも遅いし、代入もそれに近いくらい遅い、ということです・forは20倍くらい・ifは10倍ちょっと・代入は15倍くらいただし、当然forループやifの遅さと、ループ内処理の遅さの配分というか、それぞれがどれだけ時間を使ってるかは、pythonやpypyの実装(バージョン)依存だし、ループ内処理の内容にもよるので、時間配分を測定しないと、どこがどれだけ時間がかかってるのかは具体的には分かりません上記ページにも、pypyも時間がかかってpythonと時間が変わらない処理例も載ってますなので、同じコードをpythonとpypyで、細かく分けて時間を測るコードを挟みながら実行しないと、どこがどれだけ時間がかかってるのかの具体的な配分は分かりません・forループやifはpypyよりpythonが確実に遅い (10〜20倍時間かかる) ・forループ内の処理もpypyよりもpythonが時間かかってる可能性高いが、はっきりしたことは測らないと分からない(pypyも遅い場合があるので) ということです

sysy21

2020/12/16 12:20

ご回答ありがとうございます。やはりあくまでもコードやバージョン依存ということで一般化はできないという理解で次に進みたいと思います。 jbpb0さんは、修正依頼でも質問を正確に読んだ上で、初心者への配慮があり、BAとさせていただきます。回答欄に記述いただけますでしょうか。

jbpb0

2020/12/16 12:31

私は三つの質問の内で一つしか答えてないので、BAはyudedako67さんの方が相応しいと思いますよ

sysy21

2020/12/16 12:40

質問者としては両者に0.5ずつということができればと思いますが、今回はそのようにさせていただきます。ご協力ありがとうございました。

行動規範の内容に同意します

回答1件

ベストアンサー

①
ループです。一般にpypyのループはpythonと比べて桁違いに早いですし、そのコードではループが実行時間で大きな割合を占めているので、速度差の大部分はそこでしょう。

②
のぞかれた部分のi+(N-i-1)//2+1以上N-1未満のjの中にj - i == k - jを満たしうるものがありません。
kが配列外になります(j+j-i>N-1)。なのでそこまでループを回す必要はありません。

③
breakとcontinueの動作を混同してませんか?
このbreakの使い方の場合②の場合と同じようにループを打ち切るのでループの範囲が狭まります。

投稿2020/12/15 13:41

yudedako67

総合スコア2047

sysy21

2020/12/15 14:55

ご回答ありがとうございます。 ①言語仕様でループが速いというのは理解していますが、それ以上具体的にということは難しすぎますでしょうか。もしくは考えすぎでしょうか。 ②i+(N-i-1)//2+1の導出をお伺いしたいです。 ③前者だとjをインクリメントし続けてしまいますね。。解決しました。またコード表記の修正依頼を頂いた方も回答頂けると思いますので、①，②についてはもう少し他の方の回答も待ってみようと思います。

sysy21

2020/12/16 10:10

②について2*j-i<=N-1から、j<=(i+N-1)//2+1となり、下限をi+1にしているので合わせるために上限もi+(N-i-1)//2+1という表現を用いているのだと自己解決しました。 ①についてはどこまで深く言語仕様を理解しているかという問いになるかと思いますので、ある程度待ってみて回答がなければ初めに回答いただいた方をBAとさせていただきます。

行動規範の内容に同意します