質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

976閲覧

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

hiro307

総合スコア3

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2023/03/22 08:26

前提

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}

試したこと

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2023/03/22 08:45

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

2023/03/22 11:45

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

回答1

0

ベストアンサー

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}

投稿2023/03/22 08:35

編集2023/03/22 17:21
PondVillege

総合スコア1579

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hiro307

2023/03/22 11:45 編集

調べてみたところソート済みの配列の探索には二分探索を使うといいらしいのでそれを使ってみたいと思います。 100秒近くかかるとは2乗恐ろしや.... ご回答いただきありがとうございます!
hiro307

2023/03/22 12:32

ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問