| 問題 | https://paiza.jp/poh/ec-campaign |
|---|---|
| タイム一覧/C++ | http://qiita.com/cielavenir/items/a61cfe8390eb16866ae5 |
| Python/Ruby(1) | http://qiita.com/cielavenir/items/b10ff4d201150f525062 |
| C#/Java/Python/Ruby | http://qiita.com/cielavenir/items/d89e85f069cf570e6786 |
| Perl/PHP | http://qiita.com/cielavenir/items/1a650a4c41d7bdd31392 |
| JavaScript | http://qiita.com/cielavenir/items/a85b985888fdc15c52b7 |
| Go/CoffeeScript/Scala/R/Bash | http://qiita.com/cielavenir/items/79016a0afd30470f440d |
| VB/F#/D | http://qiita.com/cielavenir/items/cb6094bab56253de992c |
1: 下側を線形探索、上側を２分探索(TLE)
http://paiza.jp/poh/ec-campaign/result/6a467ff0cfce70350d24e61c271b77b3
paizapoh1_1TLE.cpp
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
int main(){
int n,d,m,i,j,r;
scanf("%d%d",&n,&d);
vi v(n);
for(i=0;i<n;i++)scanf("%d",&v[i]);
sort(v.begin(),v.end());
for(i=0;i<d;i++){
scanf("%d",&m);
if(n<2 || v[0]+v[1]>m){puts("0");continue;}
r=0;
for(r=j=0;v[j]+v[j+1]<=m&&j<n-1;j++){
vi::iterator it=upper_bound(v.begin()+(j+2),v.end(),m-v[j]);
r=max(r,v[j]+*--it);
}
printf("%d\n",r);
}
}
2: 下側を線形探索、上側を２分探索。目標金額ちょうどが見つかったらbreak (0.15s)
http://paiza.jp/poh/ec-campaign/result/a031d42262a44bd18444b411af5cfc6d
paizapoh1_2break.cpp
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
int main(){
int n,d,m,i,j,r;
scanf("%d%d",&n,&d);
vi v(n);
for(i=0;i<n;i++)scanf("%d",&v[i]);
sort(v.begin(),v.end());
for(i=0;i<d;i++){
scanf("%d",&m);
if(n<2 || v[0]+v[1]>m){puts("0");continue;}
for(r=j=0;v[j]+v[j+1]<=m&&j<n-1;j++){
vi::iterator it=upper_bound(v.begin()+(j+2),v.end(),m-v[j]);
r=max(r,v[j]+*--it);
if(r==m)break;
}
printf("%d\n",r);
}
}
3: 上限を２分探索、上側および下側を尺取り法 (0.14s)
http://paiza.jp/poh/ec-campaign/result/9af6c7dd2f3a806463965171b9741f58
paizapoh1_3shakutori.cpp
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
int n,d,m,i,j,k,r;
scanf("%d%d",&n,&d);
vector<int> v(n);
for(i=0;i<n;i++)scanf("%d",&v[i]);
sort(v.begin(),v.end());
for(i=0;i<d;i++){
scanf("%d",&m);
vector<int>::iterator it=upper_bound(v.begin(),v.end(),m-v[0]);
for(r=j=0,k=it-v.begin()-1;j<k&&v[j]+v[j+1]<=m;j++){
for(;v[j]+v[k]>m;)k--;
if(r<v[j]+v[k]){
r=v[j]+v[k];
if(r==m)break;
}
}
printf("%d\n",r);
}
}
4: バケットソートを利用 (0.11s)
http://paiza.jp/poh/ec-campaign/result/86835f040c2359d4d3cf600205ccc106
paizapoh1_4bucket.cpp
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int _v[1000001];
int main(){
int n,d,m,i,j,k,r;
scanf("%d%d",&n,&d);
vector<int> v(n);
for(i=0;i<n;i++)scanf("%d",&r),_v[r]++;
for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
for(i=0;i<d;i++){
scanf("%d",&m);
vector<int>::iterator it=upper_bound(v.begin(),v.end(),m-v[0]);
for(r=j=0,k=it-v.begin()-1;j<k&&v[j]+v[j+1]<=m;j++){
for(;v[j]+v[k]>m;)k--;
if(r<v[j]+v[k]){
r=v[j]+v[k];
if(r==m)break;
}
}
printf("%d\n",r);
}
}
5: iostreamをnosyncで使用 (0.09s)
http://paiza.jp/poh/ec-campaign/result/8a043bcbcf7531739fa9321dbcd22990
paizapoh1_5iostreamnosync.cpp
#include <iostream>
#include <algorithm>
using namespace std;
int _v[1000001],v[500000];
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,d,m,i,j,k,r;
cin>>n>>d;
for(i=0;i<n;i++)cin>>r,_v[r]++;
for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
for(i=0;i<d;i++){
cin>>m;
for(r=j=0;j<n-1&&v[j]+v[j+1]<=m;j++){
int *it=upper_bound(v+(j+2),v+n,m-v[j]);
r=max(r,v[j]+*--it);
if(r==m)break;
}
cout<<r<<endl;
}
}
6: 独自の入力関数を使用 (0.01s)
http://paiza.jp/poh/ec-campaign/result/c321cefd2014ff5411c0eb1ae19f7a91
paizapoh1_6specialget.cpp
#include <algorithm>
#include <cstdio>
char z[9999999];
int _v[1000001],v[500000];
int get(){
static int count=0;
int r=0;
for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
count++;
return r;
}
int main(){
fread(z,1,sizeof(z),stdin);
int n,d,m,i,j,k,r;
n=get(),d=get();
for(i=0;i<n;i++)_v[get()]++;
for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
for(i=0;i<d;i++){
m=get();
int *it=std::upper_bound(v,v+n,m-v[0]);
for(r=j=0,k=it-v-1;j<k&&v[j]+v[j+1]<=m;j++){
for(;v[j]+v[k]>m;)k--;
if(r<v[j]+v[k]){
r=v[j]+v[k];
if(r==m)break;
}
}
printf("%d\n",r);
}
}
ちなみに普通の２分探索でも0.01sは取れるようです。
http://paiza.jp/poh/ec-campaign/result/4ce9414275133c72d6a41e8158aad2d7
paizapoh1_7binaryfast.cpp
#include <algorithm>
#include <cstdio>
char z[9999999];
int _v[1000001],v[500000];
int get(){
static int count=0;
int r=0;
for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
count++;
return r;
}
int main(){
fread(z,1,sizeof(z),stdin);
int n,d,m,i,j,k,r;
n=get(),d=get();
for(i=0;i<n;i++)_v[get()]++;
for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
for(i=0;i<d;i++){
m=get();
for(r=j=0;j<n-1&&v[j]+v[j+1]<=m;j++){
int *it=std::upper_bound(v+(j+2),v+n,m-v[j]);
r=std::max(r,v[j]+*--it);
if(r==m)break;
}
printf("%d\n",r);
}
}
- 自作のコードで関数内staticは初めて使いました。
- upper_bound()により2分探索ができるので、最速コードの中では短い部類に入れたと思います。
- Cに6番を移植してみたところ、(upper_boundがないためk=n-1に固定され)0.11sとなってしまいました。やはりC++は強いです。