paiza POH ec-campaign (C#/Java/Python/Ruby) #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

Python/Rubyで入力を一度に読むことを実施。また、C#とJavaは標準で２分探索ライブラリを備えることがわかったので移植。

Python ※3.3でも動作

paizapoh1_read.py

#!/usr/bin/python
import sys,io,bisect
def init():
    reader = io.open(sys.stdin.fileno(),'rb',0)
    if sys.version_info[0]<3:
        s=reader.readall()
    if sys.version_info[0]>=3:
        s=str(reader.readall(),encoding='utf8')
        raw_input=input
        xrange=range
    reader.close()
    x=s.rstrip().split("\n")
    return (int(x[0].split()[0],10),[int(e,10) for e in x[1:]])

n,S=init()
v=sorted(S[0:n])
for m in S[n:]:
    r=j=0
    #k=n-1
    k=bisect.bisect_right(v,m-v[0])-1
    while j<k and v[j]+v[j+1]<=m:
        while v[j]+v[k]>m: k-=1
        if r<v[j]+v[k]:
            r=v[j]+v[k]
            if r==m: break
        j+=1
    print(r)

Ruby
paizaが更新され、bsearchの定義が不要になった。若干高速化された。やはりネイティブコード重要。

paizapoh1_read.rb

#!/usr/bin/ruby
#https://github.com/marcandre/backports/blob/master/lib/backports/2.0.0/range/bsearch.rb
unless Range.method_defined? :bsearch
  class Range
    def bsearch
      from = self.begin
      to   = self.end

      to -= 1 if exclude_end?
      satisfied = nil
      while from <= to do
        midpoint = (from + to).div(2)
        result = yield(midpoint)
        if result
          satisfied = midpoint
          to = midpoint - 1
        else
          from = midpoint + 1
        end
      end
      satisfied
    end
  end
end

S=$<.read.split("\n").map(&:to_i)
n=S[0]
v=S[1,n].sort
S[n+1..-1].each{|m|
        r=j=0
        k=((0...v.size).bsearch{|i|m-v[0]<v[i]}||v.size)-1 # upper_bound-1
        while j<k&&v[j]+v[j+1]<=m
                k-=1 while v[j]+v[k]>m
                if r<v[j]+v[k]
                        r=v[j]+v[k]
                        break if r==m
                end
                j+=1
        end
        p r
}

Java
バケットソートも入れた

paizapoh1.java

import java.util.*;
class Main{
        static final int SIZE=9999999;
        static byte[] z=new byte[SIZE];
        static int[] _v=new int[1000001],v;
        static int count=0;

        static int get(){
                int r=0;
                for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
                count++;
                return r;
        }
        public static void main(String[]Z){try{
                System.in.read(z,0,SIZE);
                int n,d,m,i,j,k,r;
                n=get();d=get();
                v=new int[n];
                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 idx=Arrays.binarySearch(v,m-v[0]+1);
                        if(idx<0)idx=~idx;
                        for(r=j=0,k=idx-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;
                                }
                        }
                        System.out.println(r);
                }
        }catch(Exception e){}}
}

C#

paizapoh1.cs

using System;
class PaizaPOH1{
    const int SIZE=9999999;
    //static string z;
    static byte[] z=new byte[SIZE];
    static int[] _v=new int[1000001],v;
    static int count=0;

    static int get(){
        int r=0;
        for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
        count++;
        return r;
    }
    public static void Main(){
        //z=Console.In.ReadToEnd();
        Console.OpenStandardInput().Read(z,0,SIZE);
        int n,d,m,i,j,k,r;
        n=get();d=get();
        v=new int[n];
        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 idx=Array.BinarySearch(v,m-v[0]+1);
            if(idx<0)idx=~idx;
            for(r=j=0,k=idx-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;
                }
            }
            Console.WriteLine(r);
        }
    }
}

• Java/C#は6番を移植したはずなのに最速にならない…。微妙なチューニングが必要なのか。
• Java/C#のbinarySearchは厳密なlower/upper_boundではないらしいので、7番は移植できないよなぁ。