PHPで競技プログラミングをしてみる(ABC067 C - Splitting Pile)

競技プログラミングの問題をPHPで解いてみたときにわかったことを整理した。

普段、競プロはc++11で解いているが、業務でPHPを使うため、PHPの勉強がてらAtCoderの問題をPHPで解いてみた。
競技プログラミングでPHPを利用している人が少ないので、この記事を期にPHP競プロerが増えたら幸いである。(ちなみに、ICPCではPHPを利用できないので注意が必要である)

ABC067 C - Splitting Pile を試しに解いてみた。
実行環境は、PHP7 (7.0.15)
まず、acceptされたコードを。

SplittingPile.php

<?php 
$N = intval(trim(fgets(STDIN)));
$tmp = trim(fgets(STDIN));
$a = array_map("intval", explode(" ", $tmp));

$l = 0;
$left = [];
$left[0] = 0;
foreach($a as $value){
    $l += $value;
    array_push($left, $l);
}

$r = 0;
$right = [];
$right[0] = 0;
$r_a = array_reverse($a);
foreach($r_a as $value){
    $r += $value;
    array_push($right, $r);
}
$right = array_reverse($right);

$ans = abs($right[1] - $left[1]);
for($i = 2;$i<count($right)-1;$i++){
    if($ans > abs($right[$i] - $left[$i])){
        $ans = abs($right[$i] - $left[$i]);
    }
}

echo $ans . PHP_EOL;

コードの解説を。

目的は、O(N^2)にならずに、左からi番目(1<=i<=N-1)のまで総和から、右からN-i番目までの総和を引いた差の最小値を求めるというもの。
累積和を使えば良さそう。

まず、標準入力で躓いた。

入力した文字列をsplit(explode)したものを配列化して、$aに格納しようとしたところ、splitしたままでは、数字が文字列として扱われてしまうから、すべて整数化しなければならなく、array_mapという関数を用いて、入力値をすべて整数化した。

このように、型指定がないため入力した文字列を整数化する必要がある。

次に、左からの累積和と右からの累積和をとった。これだと、実行時間がO(N)で間に合う。

最後に、right-leftの絶対値が、ansよりも小さいなら、ansにその絶対値を代入、みたいなことを繰り返せば、ansが求まる。

入力以外は、他の言語とやっていることが余り変わらなかった。
是非PHPで競技プログラミングを試していただきたい。