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

##先人達が残してくれた勉強方法
今日から[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)の記事を読み進めましょう！
[蟻本](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068)とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。
ここからは長い期間がかかります。

##例題 1-6-1　三角形

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

```C++: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](https://atcoder.jp/contests/abc051/tasks/abc051_b)
問題文はAtcoderを参照してください。

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

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

```C++: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++: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 )](https://atcoder.jp/contests/arc004/tasks/arc004_1)

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

```C++: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](https://atcoder.jp/contests/abc085/tasks/abc085_c)
AtCoder Beginners Editionにて解説しました。