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;
}
?>