- 基本的に、辞書を作って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を呼び出して解答しています…