AtCoderのABCで実行時間制限超過となってしまう。

前提

AtCoder Beginner Contest 294のc問題https://atcoder.jp/contests/abc294/tasks/abc294_c
についての質問です。問題のところに書いてあるサンプルのテストケースに関してはうまくいくのですが、サンプル以外のテストケースでは実行時間制限超過となってしまいます。
どこに問題があるのでしょうか？教えてください。

発生している問題・エラーメッセージ

実行時間制限超過

該当のソースコード

c++
1#include<iostream>
2#include<vector>
3#include <algorithm>
4using namespace std;
5int main(){
6  int n,m,i,j;
7  cin>>n; cin>>m;
8  vector <int> a(n); vector<int> b(m); vector<int> c(n+m);
9  
10  for(i=0;i<n;i++){
11    cin>>a.at(i);}
12  for(i=0;i<m;i++){
13    cin>>b.at(i);}
14  for(i=0;i<n;i++){
15    c.at(i)=a.at(i);}
16  for(i=0;i<m;i++){
17    c.at(i+n)=b.at(i);}
18    sort(c.begin(), c.end());
19  
20  
21  for(i=0;i<m+n;i++){
22    for(j=0;j<n;j++){
23      if(a.at(j)==c.at(i)){
24        cout<<i+1<<" ";}
25    }
26  }
27    
28  cout<<endl;
29  
30  for(i=0;i<m+n;i++){
31    for(j=0;j<m;j++){
32      if(b.at(j)==c.at(i)){
33        cout<<i+1<<" ";}
34    }
35  } 
36  
37  return 0;
38}

試したこと

少し書き方を変えてみたが時間制限超過となった。

Zuishin

2023/03/22 08:45

N と M の最大値が非常に大きいので、それを二重ループすると時間制限を超えます。サンプルでは小さい値が指定されているために通るだけです。

hiro307

2023/03/22 11:45

サンプルではすぐに通っていたのはそういうことなんですね！ありがとうございます！

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

回答1件

ベストアンサー

M, Nがそれぞれ10^5あるにも関わらず，21-26行目および30-35行目の操作がそれぞれO((N + M)N)およびO((N + M)M)なのでTLEになります．

C++
1for(i = 0; i < m + n; i++) { // O(N + M)
2    for(j = 0; j < n; j++) { // O(N)
3         if(a.at(j) == c.at(i)) cout << i + 1 << " ";
4    }
5}
6    
7cout << endl;
8
9for(i = 0; i < m + n; i++) { // O(N + M)
10    for(j = 0; j < m; j++) { // O(M)
11         if(b.at(j) == c.at(i)) cout << i + 1 << " ";
12    }
13}

展開してO(N^2 + NM)及びO(NM + M^2)なので，N, Mいずれも10^5だった場合10^10となります．C/C++では1秒間に10^7~10^8回程度しかループを回せないので100秒から1000秒近くかかる実装です．

一般に，貴回答のことを愚直(実装)解と呼びますが，C問題で愚直解はほとんど通りません．

したがって，2乗のループをどうにかして改善してO((N + M)X)のXを対数時間や定数時間で実装してください．
現状，Xに位置するアルゴリズム(22-25行目，31-24行目)が線型探索となっており，ソート済み配列を探索するアルゴリズムとして非常に低速なものとして知られています．

C++
1for(i = 0; i < m + n; i++) { // O(N + M)
2    // ここをO(N)未満で実装する
3}
4    
5cout << endl;
6
7for(i = 0; i < m + n; i++) { // O(N + M)
8    // ここをO(M)未満で実装する
9}