paiza POH hundred_thousand #_poh

• 基本的に、辞書を作って2分探索だと思う。
• ただ、この辞書を作る処理が割と重い。もう少し効率的にならないだろうか…。

10.cpp

#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
    int M,N;
    scanf("%d%d",&N,&M);
    vector<long long>v(M),q(N),s;
    s.reserve(M*M/2);
    for(int i=0;i<N;i++)scanf("%lld",&q[i]);
    for(int i=0;i<M;i++)scanf("%lld",&v[i]);
    sort(v.begin(),v.end());
    long long z=*max_element(q.begin(),q.end())+999;
    for(int i=0;i<M;i++)for(int j=i;j<M;j++){if(v[i]*v[j]>z)break;s.push_back(v[i]*v[j]);}
    sort(s.begin(),s.end());
    for(auto &x:q)printf("%lld\n",*lower_bound(s.begin(),s.end(),x)-x);
}

10.rb

#!/usr/bin/ruby
N,M,*Q=`dd`.split.map &:to_i
V=Q.pop(M).sort
Z,*S=Q.max+999
M.times{|i|(i...M).all?{|j|V[i]*V[j]<Z&&S<<V[i]*V[j]}}
S.sort!
Q.map{|x|p S.bsearch{|e|e>=x}-x}

複数言語

他の言語は、systemなりexecなりでRubyを呼び出して解答しています…