paiza POH ec-campaign #paizahack_01 (Go/CoffeeScript/Scala/R/Bash)

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

Go
2分探索は標準のもののほうが速いっぽい。まあ、そうですよね。

paizapoh1.go

package main
import(
    "fmt"
    "os"
    "text/scanner"
    "strconv"
    "sort"
)

var sin scanner.Scanner
func scanint() int{
    sin.Scan()
    ret,_ := strconv.Atoi(sin.TokenText())
    return ret
}

/*
func array_binarysearch(needle int,haystack []int,size int) int{
    high := size-1
    low := 0
    ret := size
    for low <= high {
        probe := (high + low) / 2
        comparison := haystack[probe]-needle
        if comparison <= 0 {
            low = probe+1
        }else{
            ret=high
            high = probe-1
        }
    }
    return ret
}
*/

func main(){
    sin.Init(os.Stdin)
    n:=scanint()
    d:=scanint()
    _v:=make([]int,1000001)
    v:=make([]int,n)
    for i:=0;i<n;i++ { _v[scanint()]++ }
    i:=0
    for j:=0;j<1000001;j++ {
        for k:=0;k<_v[j];k++ { v[i]=j;i++ }
    }
    for i=0;i<d;i++ {
        m:=scanint()
        //idx:=array_binarysearch(m-v[0],v,n)
        idx:=sort.Search(n,func(i int) bool{return m-v[0]<v[i]})
        r:=0
        j:=0
        k:=idx-1
        for r<m&&j<k&&v[j]+v[j+1]<=m {
            for v[j]+v[k]>m {k--}
            if r<v[j]+v[k] {r=v[j]+v[k]}
            j++
        }
        fmt.Println(r)
    }
}

CoffeeScript

paizapoh1.coffee

#!/usr/bin/env coffee
T=[]
stdin = process.openStdin()
stdin.setEncoding('utf8')

array_binarysearch = (needle,haystack,size) ->
    high = size-1
    low = 0
    ret = size
    while low <= high
        probe = (high + low) / 2^0
        comparison = haystack[probe]-needle
        if comparison <= 0
            low = probe+1
        else
            ret=high;
            high = probe-1;
    return ret

input_fragment=''
stdin.on 'data', (input) ->
        ref=(input_fragment+input).split("\n")
        input_fragment=ref.pop()
        for i in [0...ref.length]
            if ref[i]==''
                continue
            T.push(ref[i])


stdin.on 'end', (z) ->
    if input_fragment
        ref=(input_fragment+"\n").split("\n")
        input_fragment=ref.pop()
        for i in [0...ref.length]
            if ref[i]==''
                continue
            T.push(ref[i])
    arg=T[0].split(' ').map(Number)
    n=arg[0]
    d=arg[1]
    v=T.slice(1,1+n).map(Number).sort (a,b) ->
        return a-b
    for i in [0...d]
        m=Number(T[1+n+i])
        idx=array_binarysearch(m-v[0],v,n)
        r=0;
        j=0;
        k=idx-1
        while r<m&&j<k&&v[j]+v[j+1]<=m
            while v[j]+v[k]>m
                k--
            if r<v[j]+v[k]
                r=v[j]+v[k]
            j++
        console.log r

Scala
binarySearchを使うとばぐるっぽい。手元では大丈夫なんだけど。

paizapoh1.scala

//import scala.collection.JavaConversions._
object Main extends App{
    val Array(n,d) = readLine().split(" ").map(_.toInt)
    val _v=new Array[Int](1000001)
    val v=new Array[Int](n)
    for(i<-0 to n-1)_v(readInt())+=1
    var i=0
    for(j<-0 to 1000000)for(k<-0 to _v(j)-1){
        v(i)=j
        i+=1
    }
    for(i<-0 to d-1){
        val m=readInt()
        var idx=n//java.util.Arrays.binarySearch(v,m-v(0)+1)
        if(idx<0)idx=(~idx)
        var r=0
        var j=0
        var k=idx-1
        while(r<m&&j<k&&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)
                }
                j+=1
        }
        println(r)
    }
}

R
まあ、TLEになる予想はできていた。

paizapoh1.R

#!/usr/bin/env Rscript
x=scan("stdin")
n=x[1]
d=x[2]
v=sort(x[3:(2+n)])
t=x[(3+n):length(x)]
for(i in 1:length(t)){
    m=t[i]
    idx=n+1
    r=0
    j=1
    k=idx-1
    while(r<m&&j<k&&v[j]+v[j+1]<=m){
        while(v[j]+v[k]>m)k=k-1
        if(r<v[j]+v[k]){
            r=v[j]+v[k]
        }
        j=j+1
    }
    cat(r)
    cat("\n")
}

Bash
遅すぎて使い物になりませぬ。
senpai-tasuketeによる計測ですら1分かかってます。
あとpaizaで謎のランタイムエラーになる。問い合わせ中。

paizapoh1.sh

#!/bin/sh
#set -e
#https://gist.github.com/oliverdaff/6067071
binary_search(){
    TARGET=$1
    TO_SEARCH=(${v[@]}) #(${@:2})
    LENGTH=${#TO_SEARCH[@]}

    RETURN=$LENGTH
    START=0
    END=$((LENGTH - 1))
    while [[ $START -le $END ]]; do
        MIDDLE=$(((START + END)/2))
        ITEM_AT_MIDDLE=${TO_SEARCH[MIDDLE]}
        if [[ $ITEM_AT_MIDDLE -le $TARGET ]]; then
            START=$((MIDDLE+1))
        else
            RETURN=$END
            END=$((MIDDLE-1))
        fi
    done
    echo $RETURN
}

read line
a=($line)
n=${a[0]}
d=${a[1]}
#v=()
#i=0
#input n
#while [ $i -ne $n ];do
#   read line
#   v=("${v[@]}" $line)
#   i=`expr $i + 1`
#done
#sort
orig_ifs=$IFS
IFS=$'\n'
_v=($(cat))
v=($(echo "${_v[*]:0:$n}" | sort -n))
IFS=$orig_ifs
t=("${_v[@]:$n:$d}")
i=0
while [ $i -ne $d ];do
    m=${t[$i]}
    idx=$(binary_search $((m-v[0])))
    r=0
    j=0
    k=$((idx-1))
    while [ $r -lt $m ] && [ $j -lt $k ] && [ $((v[j]+v[j+1])) -le $m ];do
        m_minus_vj=$((m-v[j]))
        while [ ${v[k]} -gt $m_minus_vj ];do
            k=$((k-1))
        done
        vj_minus_vk=$((v[j]+v[k]))
        if [ $r -le $vj_minus_vk ];then
            r=$vj_minus_vk
        fi
        j=$((j+1))
    done
    echo $r
    i=$((i+1))
done