paiza POH ec-campaign #paizahack_01

|問題|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|

|言語|タイム|URL|備考|
|:--|:--|:--|:--|
|C++|**0.01s**|http://paiza.jp/poh/ec-campaign/result/c321cefd2014ff5411c0eb1ae19f7a91| |
|C/ObjC|**0.01s**|http://paiza.jp/poh/ec-campaign/result/5bae3b864a7e2e73689ec90e43ca52a0<br>https://paiza.jp/poh/ec-campaign/result/c05fae683f33debee7044d0efc71f80f|2分探索はPHPの解答から持ってきた|
|D|**0.01s**|https://paiza.jp/poh/ec-campaign/result/a66dd68fcf1ce93973dbeeca97261a20| |
|Go|0.03s|https://paiza.jp/poh/ec-campaign/result/e068f4bb29f7222d175f3bd7d14f8b6a|Cから移植|
|Rust|0.03s|https://paiza.jp/poh/ec-campaign/result/84206998| |
|VB|0.04s|https://paiza.jp/poh/ec-campaign/result/f64b8421232ce8af44af2257aca53372|C#より速いのはコンパイラのバージョンが上がったためかも。|
|Swift|0.06s|https://paiza.jp/poh/ec-campaign/result/7d2fd249|Cから移植|
|C#|0.08s|http://paiza.jp/poh/ec-campaign/result/001cced3bd0535d7f582ab16605a51e1| |
|F#|0.10s|http://paiza.jp/poh/ec-campaign/result/66ba3d32fcbf1c1f2d89e27024e23971| |
|Java|0.11s|http://paiza.jp/poh/ec-campaign/result/5242df8f0e4a2d2e66a0baff01c8261e| |
|Swift|0.11s|http://paiza.jp/poh/ec-campaign/result/2a07c3a1| |
|Kotlin|0.12s|https://paiza.jp/poh/ec-campaign/result/bf85fd60| |
|Bash|0.16s|http://paiza.jp/poh/ec-campaign/result/59b1c2715ba915f358065ae75ad91588|Ruby埋め込み|
|Ruby|0.16s|http://paiza.jp/poh/ec-campaign/result/824100fd0384855f070b977b756a0280|バケットソート不使用|
|Perl|0.19s|http://paiza.jp/poh/ec-campaign/result/2888e41dcc83385589a3f4fca9f046ca|バケットソート・全読み不使用、2分探索は非標準モジュール|
|JavaScript|0.19s|https://paiza.jp/poh/ec-campaign/result/9b5f290af9af44b9aac1c0786e5a4cc9|バケットソート不使用、2分探索はCから移植|
|CoffeeScript|0.27s|https://paiza.jp/poh/ec-campaign/result/6bf4b991d94a306efbe54ca2535584ff|バケットソート不使用、2分探索はCから移植|
|Python2/Python3|0.33s<br>0.51s|http://paiza.jp/poh/ec-campaign/result/29c3004ca1495a9cc17bcc7e49dc0ee0<br>https://paiza.jp/poh/ec-campaign/result/9fbe58575d7e15bf4e500d46f5f5a7fe|バケットソート不使用|
|Scala|0.60s|https://paiza.jp/poh/ec-campaign/result/77ec8815f70cff0df12ed857bbac2366|2分探索を使うとばぐるっぽいので不使用|
|PHP|0.82s|http://paiza.jp/poh/ec-campaign/result/e3ed756743e7265c2ad23440dede0e45|バケットソート・全読み不使用、2分探索はサンプルコード|
|R|TLE|https://paiza.jp/poh/ec-campaign/result/6cf2fc4bd5385323f02ce60d38448036|バケットソート・2分探索不使用|

1: 下側を線形探索、上側を２分探索(TLE)
http://paiza.jp/poh/ec-campaign/result/6a467ff0cfce70350d24e61c271b77b3

```cpp: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

```cpp: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

```cpp: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

```cpp: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

```cpp: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

```cpp: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

```cpp: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++は強いです。