プログラミングコンテスト攻略のためのアルゴリズムと攻略方法

プログラミングコンテスト攻略のためのアルゴリズムと攻略方法 P114 データ構造の応用

global $ch;

$ch = '\\\\///\\_/\\/\\\\\\\\/_/\\\\///__\\\\\\_\\\\/_\\/_/\\';

$ch = str_split($ch);
//print_r($ch);
function main(){

global $ch;
$a = 0;
$s1 = [];
$s2 = [];
$sum = 0;//水たまりの総面積
for($i =0;$i < count($ch);++$i){ //echo $ch[$i].PHP_EOL; if($ch[$i] == "\\"){ $s1[] = $i; } elseif($ch[$i] == "/" and count($s1) > 0){
$j = array_splice($s1,count($s1) -1,1);
//echo $j[0].PHP_EOL;
$s1 = array_merge($s1);
$sum += $i-$j[0];
$a = $i - $j[0];
while(count($s2) > 0 and $s2[count($s2)-1][0] > $j){
$a += $s2[count($s2)-1][1];
array_splice($s2,count($s2)-1,1);
}
$s2[] = [$j,$a];
}
}

$t = 0;
$s2 = array_merge($s2);
//print_r($s2);

echo "$sum".PHP_EOL;
echo count($s2);
echo " ";
for($i = 0;$i < count($s2);$i++){ echo $s2[$i][1]; echo " "; } echo "\n"; } main(); //35 //5 4 2 1 19 9 //と出力

      

コメント