CoffeeScript
Go
Scala
Bash
R

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

More than 1 year has passed since last update.

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