AtcoderでTLEを吐かれたが模範解答より劣っている点がわからないです

Question

#実際の問題と現状
実際の問題
こちらのつい先日行われたABCのC問題なのですが、TLEが出てしまい、それが今でもなぜかがわからないです。C++で書かれた模範解答は自分の力不足で読めなかったのですが、Pythonのほうは特に知らないライブラリが使われているわけではなかったので読むことができたのですが、自分の書いたC++のコードとそれほどアルゴリズムに違いはないように感じられ(むしろ現時点では自分は早いとすら思っています)どこがボトルネックになっているのかが自分の知識ではわからないです。それを教えていただけると非常にありがたいです

実際の問題文(詳細は上のリンクからお願いします)
「N個の文字列 S1,S2,…,SNが与えられます。 各文字列は、英小文字からなる空でない文字列の先頭に ! を 0文字か 1文字付加したものです。文字列 Tは、Tの先頭に!を0文字付加しても1文字付加しても S1,S2,…,SNのいずれかに一致するとき、不満な文字列であるといいます。不満な文字列があるかどうか判定し、あれば 1つ示してください。」(なお、なければ"satisfiable"と出力します)
#模範解答と自分のコード
模範解答

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<string> S(N);
    for(string& s : S) cin >> s;
    unordered_set<string> h(S.begin(), S.end());
    for(string& s : S) if(h.count('!' + s)){
        cout << s << endl;
        return 0;
    }
    cout << "satisfiable" << endl;
}

N = int(input())
S = set(input() for i in range(N))
for s in S:
    if "!" + s in S:
        print(s)
        exit()
print("satisfiable")

自分の回答

#include <bits/stdc++.h>
 
#define _GLIBCXX_DEBUG
 
using namespace std;
 
/* const int INF = 1000000000; */
 
int main(){
   int N;
   cin >> N;
 
   vector<string> S(N);
 
   for (int i=0; i<N; i++)
       cin >> S[i];

   /* sort(S.begin(), S.end()); */
   /* reverse(S.begin(), S.end()); */

   string T;
   string output = "satisfiable";
   int flag = 0;
 
   for (int i=0; i<N; i++){
       if (S[i][0] == '!')
           continue;
       T = "!" + S[i];
       for (int j=0; j<N; j++){
           if (T == S[j]){
               output = S[i];
               flag ++;
               break;
           }
       }
       if (flag == 1)
           break;
   }
  cout << output; 
}

※補足
問題文から、!!hogehogeのような文章は生成されないため、!始まりのものを抜くことで高速化を図りました。vectorのアクセスの計算量はO(1)と見かけたのでそれほど影響はないと思ってます。
逆順にソートすることで!から始まるかどうかを判別せずに済むと思ったので念の為に追加してみましたがソートのほうが時間かかってるようだったので外しました。
INFはDP使うとき用に残しているだけで特に使用していないので誤解を招かないようにコメントアウトしておきました。本番はコメントアウトは特にしなかったです。

Comments

[Zuishin]

読んでいませんが、TLE なら無限ループかオーバーフローを疑ってください。たとえば long long が必要な時に int を使っていると TLE になりがちです。

[renge]

テストケースが32件あり、ソートを導入したりアルゴリズムを変更したりしてACが15-20の範囲で変動したのですが、無限ループは考えられますかね？また、forループしか使用していないので無限ループの可能性は低い気がします。(自分の知識不足でしたら申し訳ないです)
また、オーバーフローでTLEになるのは盲点でしたのでNと念の為にflagもlong longにしてみましたが結果は同様にTLEとなってしまいました。(念の為にflag++をflag=1にしたりもしましたが同じ結果でした)

[Zuishin]

無限ループではないようですね。O(N^2) なので、模範解答よりかなり効率が悪いコードです。N は最大 2 × 10^5 なので、大きな N が与えられれば時間オーバーする可能性はありますね。

[renge]

あ、PythonでもO(N^2)だと思っていましたが、集合をつかうと検索がO(N)ではなくO(1)で行えるのですね。理解しました。ありがとうございました。回答欄に来ていただいてBAをつけさせていただいてもよろしいでしょうか？

Answer 1

最大 2 × 10^5 の二重ループを行っているためと思われます。
模範解答は一重なので、実行時間に差が出るでしょう。

Comments

[renge]

改めてありがとうございました！一ヶ月ほど前に、オブジェクト指向を使うことについての質問の際にもお世話になりました。また機会がありましたらよろしくおねがいします

[Zuishin]

なお、次のサイトを参考にすると、蟻本では次のような目安が書かれているそうです。

https://cppx.hatenablog.com/entry/2017/08/06/104144

> 制限時間が1秒の場合、
> 10の6乗　余裕を持って間に合う
> 10の7乗　おそらく間に合う
> 10の8乗　非常にシンプルな処理でない限り厳しい

[renge]

なるほどです。わざわざありがとうございます。参考になります