PHPでも競技プログラミングがしたい！

この記事はチームラボエンジニアリングアドベントカレンダー5日目の記事です。
昨日の記事は、@tsuruken さんによるSeleniumで業務のテストを自動化しようと試みた話でした。
テスト自動化、大切ですよね......！

##はじめに
今年からwebエンジニアとして働き始め、9月から案件でPHP使うようになりました。
そこでPHPにたくさん触れて慣れたいと思ったので、競技プログラミング(AtCoder)をPHPで始めてみました。
実際にやってみるとC++で書く人が多く、動的型付け言語、さらにPHPとなると圧倒的に少数派なのが現状です。
そこでPHPでも競技プログラミングが始めやすいように入力、例題についてまとめてみました。
PHPを使っている方が競技プログラミングを始めるきっかけになれば幸いです。

##入力について
いまだに入力に手こずっている雑魚なのでさっくりまとめてみました！これをコピペでいけるはず！

####入力　1行のみの場合

入力例
1 2 3 4 5
こちらの入力をintの配列にしていきたいと思います。

<?php

// 標準入力（STDIN）から1行読み込み（fgets）をしてinputに代入します
$input = fgets(STDIN);  // $input = "1 2 3 4 5"

// 取得した値を半角スペースで分解します（PHPのsplit的な関数） とりあえずこれで十分扱えます!
$input_array = explode(" ", $input); // $input_array = [ "1" , "2" , "3" , "4" , "5"]

// 厳密な比較をしたい時などキャストしておきたい時などはこちら、型変換はintval()より(int)を使う方が早いらしい
$int_array = array_map( function($value) { return (int)$value; }, $input);

####入力　複数行の場合
入力例(2行だけ)
あいうえお かきくけこ

fgets()は読み込むごとに1行ずつ読み込んでくれるので2行の場合はこんな感じに書くだけでうまく読み込んでくれます。

<?php
// 標準入力からの入力値を変数に代入します
$input１ = fgets(STDIN);  // $input1 = "あいうえお"
$input２ = fgets(STDIN);  // $input2 = "かきくけこ"

####入力　N行で1行に複数の値を渡される時
https://atcoder.jp/contests/dp/tasks/dp_c
こういう問題ですね。これも扱えるようになればだいたい入力はいけます。

入力例

$N $
$a_1　b_1　c_1$
$a_2　b_2　c_2$
...
$a_N　b_N　c_N$

<?php
$n=trim(fgets(STDIN));
for($i=0;$i<$n;++$i){
	// fscanf(）...フォーマットに基づいて入力を処理する
	fscanf(STDIN,"%d %d %d",$x,$y,$z);
	$a[$i]=$x;  // aのみが入る配列
	$b[$i]=$y;  // bのみが入る配列
	$c[$i]=$z;  // cのみが入る配列
}

##問題を解いてみる

入力ができるようになったらこちらの問題を解いて入出力に慣れましょう！
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

これPHPで解いたらネタになるんじゃないかと思ったらすでにありました・・・
AtCoder に登録したら解くべき精選過去問 10 問を PHP で解いてみた

いい記事でした、すっきり書かれていて勉強になります。
これをやれれば簡単なアルゴリズムの考え方はわかってくるかと思います。

##DPを解いてみよう

次は代表的なアルゴリズムの一つである動的計画法を解けるようになりましょう！
超絶初心者なので全然スマートな書き方ではないですが解答例も載せました、参考程度に・・・

###問題を解いてみる（動的計画法１）
問題はこちら。
https://atcoder.jp/contests/dp/tasks/dp_b
カエルが高さのある足場をジャンプしていき、もっとも疲れないルートを見つけるという問題です。
とても可愛いですね。
難しそうと思ったらこれよりも簡単な問題もあるのでこちらから解いてみるのもおすすめです。
早速PHPでの解答例を載せます。

####解答例

<?php
$first_line = fgets(STDIN);
$second_line = fgets(STDIN);
$first_line_array = explode(" ", $first_line);

// 足場の数の合計
$steps_amount = $first_line_array[0];
// ジャンプで飛べる足場の数
$skip_power = $first_line_array[1];
// 足場の高さの配列
$steps_heights = explode(" ", $second_line);
// 足場ごとにたどり着くまでのコストの総和の最小値を入れていく配列
$dps = [];

foreach (range(0, $steps_amount - 1) as $index) {

    // 最初にいた足場に辿り着くまでのコストは０
    if ($index === 0) {
        $dps[0] = 0;
        continue;
    }

    // 一つ前の踏み台につくまでの総コスト
    $previous_total_cost = $dps[$index - 1];
    // 一つ前の踏み台から飛ぶためのコスト
    $jump_cost = abs($steps_heights[$index] - $steps_heights[$index - 1]);
    // とりあえず一つ前の踏み台から飛んだ場合の総コストで初期化して、数を比較して最小値を入れていく
    $dps[$index] = $previous_total_cost + $jump_cost;

    // 足場を飛ばした場合のことを考える
    foreach (range(1, $skip_power) as $i) {
        if ($index >= $i) {
            $new_total_cost = abs($dps[$index - $i] + abs($steps_heights[$index] - $steps_heights[$index - $i]));
            // 足場を飛ばした時のコストの方が少ない場合は値を更新する
            if ($dps[$index] > $new_total_cost) {
                $dps[$index] = $new_total_cost;
            }
        }
    }

}

//最後の足場の総コストを出力
echo end($dps);

####問題を解いてみる（動的計画法2）
お次はこちら
https://atcoder.jp/contests/dp/tasks/dp_d
ナップザック問題と呼ばれる動的計画法の有名問題です。
ちょっととっつきづらいので他の方が書いた素晴らしい解説を載せておきます。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～

PHPでの解答例を載せます。

####解答例

<?php
$first_line = fgets(STDIN);
// 取得した入力値を半角スペースで分解します
$first_line_array = explode(" ", $first_line);
//複数の変数に値を一括代入する
list($item_num, $weight_upper) = $first_line_array;

for ($i = 0; $i < $item_num; ++$i) {
    fscanf(STDIN, "%d %d ", $x, $y);
    $weight[$i] = $x;
    $value[$i] = $y;
}

$dp = [];
// 使うアイテムが０個だった場合から一つずつアイテムを増やして検討していく
foreach (range(0, $item_num - 1) as $item_index) {
    $i_value = $value[$item_index];
    $i_weight = $weight[$item_index];
    // リュックが許容する重さが０だった場合から検討していき増やして検討していく
    foreach (range(1, $weight_upper) as $weight_index) {
        // $current_value = isset($dp[$item_index - 1][$weight_index]) ? $dp[$item_index - 1][$weight_index] : 0;と同じ意味です、便利ですね
        $current_value = $dp[$item_index - 1][$weight_index] ?? 0;
        if ($weight[$item_index] <= $weight_index) {
            $new_value = (($dp[$item_index - 1][$weight_index - $weight[$item_index]] ?? 0) + $i_value);
            $dp[$item_index][$weight_index] = $current_value >= $new_value ? $current_value : $new_value;
        } else {
            $dp[$item_index][$weight_index] = $current_value;
        };
    }
}
echo $dp[(int)$item_num - 1][(int)$weight_upper];

##PHPで競技プログラミングをやってみて
連想配列のみで純粋な配列がなかったり、if(0 == "-")がtrueになったり、少しゆるいところもありますが、あんまり厳密な書き方をしなくてよくて、分かりやすい言語だと感じました。

モビルスーツの性能の違いが、戦力の決定的差ではないということを・・・教えてやる！

と昔の人も言っていたので、漸進的型付けなど学んで、もっとPHPを使いこなせるようになろうと思いました！