最も基本的な for 文型の全探索

先人達が残してくれた勉強方法

今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。
ここからは長い期間がかかります。

例題 1-6-1　三角形

• 3重ループとしてO(n^3)
• 100^3は1000000なので実行時間１秒としても余裕で間に合います
• 斜辺が他の２辺より長い時だけ三角形が作成できる

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    vector<int> a(n, 0);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    int ans=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                int len = a[i]+a[j]+a[k];
                int m = max(a[i], max(a[j], a[k]));
                int rest = len - m;

                if(m > rest){
                    ans = max(ans, len);
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

B - Sum of Three Integers

問題文はAtcoderを参照してください。

• まず考えるのは、2<= K <= 2500
• 0 <= s <= 3K
• O(N^3)は15,625,000,000です。
• 100,000,000を超えると実行時間1sに間に合いません。

下記のような全探索は間に合いません。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n, s;
    cin >> n >> s;

    int ans=0;
    for(int x=0; x<=n; x++){
        for(int y=0; y<=n; y++){
            for(int z=0; z<=n; z++){
                if(x+y+z==s){
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

ここで考えるのは、　x＋y＋z＝＝sはs-(x+y)=zにできることです。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n, s;
    cin >> n >> s;

    int ans=0;
    for(int x=0; x<=n; x++){
        for(int y=0; y<=n; y++){
            int z=s-(x+y);

            if(0<=z && z<=n){
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

• O(N^2)は16,250,000です。
• 1000万の処理なら、重い処理意外なら間に合います。

ACで通りました。

A - 2点間距離の最大値 ( The longest distance )

• 2<= N <= 100
• O(N^2)で100^2なら全探索で間に合う
• アルゴリズムいらない？

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    vector<int> x(n, 0);
    vector<int> y(n, 0);

    for(int i=0; i<n; i++){
        cin >> x[i];
        cin >> y[i];
    }

    double ans=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            int xx = pow(abs(x[j]-x[i]), 2);
            int yy = pow(abs(y[j]-y[i]), 2);
            double p = sqrt(xx+yy);

            ans = max(ans, p);
        }
    }

    cout << ans << endl;
    return 0;
}

ACで通りました。

C - Otoshidama

AtCoder Beginners Editionにて解説しました。