##先人達が残してくれた勉強方法
今日からAtCoder 版!蟻本 (初級編)の記事を読み進めましょう!
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。
ここからは長い期間がかかります。
##例題 1-6-1 三角形
- 3重ループとしてO(n^3)
- 100^3は1000000なので実行時間1秒としても余裕で間に合います
- 斜辺が他の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> 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にて解説しました。