paiza POH ec-campaign (Perl/PHP) #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

Perl
ついに非標準モジュールに手を出してしまいました。

paizapoh1.pl

#!/usr/bin/perl
use strict;
use warnings;
use feature qw(say);

BEGIN{
	eval qq(use List::BinarySearch qw(binsearch_pos););
	if($@){
		#warn 'falling back to Perl binsearch_pos.';
		sub binsearch_pos (&$\@) {
			my ( $comp, $target, $aref ) = @_;
			my ( $low, $high ) = ( 0, scalar @{$aref} );
			while ( $low < $high ) {
				my $cur = int( ( $low + $high ) / 2 );
				no strict 'refs';  ## no critic(strict)
				local ( ${ caller() . '::a'}, ${ caller() . '::b'} ) = ( $target, $aref->[$cur] );
				if ( $comp->( $target, $aref->[$cur] ) > 0 ) {
					$low = $cur + 1;
				} else {
					$high = $cur;
				}
			}
			return $low;
		}
	}
}

my($n,$d)=split(' ',<>);
my @v=();
for(my $i=0;$i<$n;$i++){push(@v,int($_=<>))};
@v=sort{$a<=>$b}@v;
for(my $i=0;$i<$d;$i++){
	my $m=int(<>);
	my ($r,$j)=(0,0);
	my $idx=binsearch_pos {$a<=>$b} $m-$v[0]+1, @v;
	for(my $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];
			last if($r==$m);
		}
	}
	say $r;
}

PHP
その関数どこから拾ってきた…。

paizapoh1.php

#!/usr/bin/php
<?php
//http://www.php.net/array_search#93352
function array_binarysearch($needle, $haystack){
    $high = count( $haystack )-1;
    $low = 0;
    $ret = count($haystack);
    while( $high >= $low ){
        $probe = floor( ( $high + $low ) / 2 );
        $comparison = $haystack[$probe]-$needle;
        if( $comparison <= 0 ){
            $low = $probe+1;
        }else{
			$ret=$high;
            $high = $probe-1;
        }
    }
	return $ret;
}

list($n,$d)=explode(' ',fgets(STDIN));
$v=array();
for($i=0;$i<$n;$i++)array_push($v,intval(fgets(STDIN)));
sort($v);
for($i=0;$i<$d;$i++){
	$m=intval(fgets(STDIN));
	$idx=array_binarysearch($m-$v[0],$v);
	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;
		}
	}
	echo $r.PHP_EOL;
}
?>