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