AtCoderで得たPHP知識

PHPでAtCoderをやっています。
AtCoderにおいては初心者（茶色コーダー）ですが、PHPでいろいろと学びがあったので書きます。

AtCoderとは

テレ東のYouTube動画が分かりやすいです。

ざっくり言うと、7問のプログラミングの問題が出題され、それを100分以内に解きます（毎週開催されるビギナーコンテストの場合）。
その解けた数や回答時間の早さで順位が付き、レーティング（点数）が変化していきます。

コンテストの種類によって、問題数やコンテスト時間、難易度、出場可能な資格（レーティング）などが変わってきます。
ビギナーコンテストで、7問中3問解ければ、おおよそ茶色コーダーです。

環境構築について

AtCoderのサイト上に、コードテストできる環境があるのですが、競技時間中はアクセスが集中し、テスト結果がなかなか返ってきません。
このため、ローカル環境でテストできるようにしておくと便利です。

すでにPHPを使っている方なら、PCにPHPの実行環境はあると思います。
他に、php-gmpをインストールしておくと良いです。
（AtCoderで使える外部ライブラリについては、後述します）

テストには、PHPUnitなどを使うのが良いのかもしれませんが、わたしには標準入力をユニットテストする方法が分からなかったので、以下のようなシェルスクリプトをChatGPTに書いてもらいました。
(Linuxで動かしています）

#!/bin/bash
input1="1 2 3 4 5

"
input2="

"
input3="

"
echo -e "$input1" | php ./ans.php
# echo -e "$input2" | php ./ans.php
# echo -e "$input3" | php ./ans.php

回答案をans.phpに書き、同じフォルダに置いた上記のシェルスクリプトを実行することで、テストできます。
入力例がたくさんある問題のときは、input2や3も使います。
実行のパーミッションが必要なので、chmod +x シェルスクリプトのファイル名 などで実行権限を与えてください。

標準入出力について

PHPの通常の使い方は、ブラウザへのHTML出力だと思いますが、AtCoderでは標準入出力に慣れる必要があります。
とはいえ、難しくはありません。

標準入力は、trim(fgets(STDIN)) を使う

詳しくは、「PHPでも競技プログラミングがしたい！」が分かりやすいです。

<?php
$input = trim(fgets(STDIN));  // この時点ではstring型なので注意する
$num = (int) $input;  // 整数値の場合は、int型にキャストできます

なお、空白区切りの文字列を配列にするときは explode なのに、詰まった文字列のときは str_split なので注意します。

<?php
$whitespace = 'a b c';
var_dump(explode(' ', $whitespace));
// ['a','b','c']
$str = 'abc';
var_dump(str_split($str));
// ['a','b','c']

標準出力は、できるだけ1つにまとめる

標準出力は、echoするだけなのですが、echo1回の時間はそれなりにあります。
echoは、1行で複数の文字列を出力できます。
しかし、複数回echoするよりも、できるだけ連結してからechoした方が、処理が速いです。

<?php
$num = 10 ** 6;
for($i = 0; $i < $num; $i++) {
    echo $i, 'a';  // 2 * 10 ** 6 回 echo
}
// 実行時間：1746 ms

<?php
$num = 10 ** 6;
for($i = 0; $i < $num; $i++) {
    echo $i. 'a';  // 10 ** 6 回 echo
}
// 実行時間： 927 ms

<?php
$num = 10 ** 6;
$ans = '';
for($i = 0; $i < $num; $i++) {
    $ans .= $i. 'a';
}
echo $ans;  // 1 回 echo
// 実行時間：  88 ms

配列を出力する場合は、implode が便利です。
処理時間の制限が厳しいとき、出力回数の削減は大事です。

AtCoderで使えるライブラリ

2024年12月時点で使える外部ライブラリは、以下の通りです。

• GMP
• BCMath
• SQLite3

最新の情報は、こちら にあります。

わたしはこれまで、BCMathとSQLite3を使ったことがありません。
（BCMathは桁数の大きな計算に使うようで、SQLite3はデータベースのようです。AtCoderでの便利な使い方をご存じの方は教えてください）

一方、GMPは、ときどき使います。
また、SPL（スタンダードPHPライブラリ）も使います。
SPLは、標準ライブラリなので、インストールせずに使えます。

以下、便利なライブラリの使い方を紹介します。

nの階乗を計算したい（gmp_fact）

場合の数で、計算量をおおよそ見積もりたいことがあります。
このようなとき、1からnまでの階乗（n! = 1 * 2 * ... * n）が必要になるので、gmp_factが便利です。

<?php
echo gmp_fact(10);
// 3628800 (= 10! = 1 * 2 * ... * 10 が出力されます)

幅優先探索したい（SplQueue）

最短経路を調べたりするときに、幅優先探索（BFS）をしたいときがあります。
このようなときは、キュー（順番に処理する）構造を、SplQueueクラスで実装できます。
メソッドは、enqueueとdequeue、isEmptyだけ覚えれば良いので、これを使うのが楽です。

<?php
// このコードはイメージなので、このままでは動きません
$graph = ['何かグラフを表現する配列'];
$visited = [];
$que = new SplQueue();
while(!$que->isEmpty()){
    $current = $que->dequeue();
    // $currentで判定や処理する
    if(hasNextQueue($current)) {
        $que->enqueue(NextQueue($graph, $current));
    }
    $visited[] = $current;    
}

上記はイメージなので、hasNextQueueやNextQueueなど、架空のユーザー定義関数を作っていますが、コンテスト中はこれらの実装がとても難しいです。

なお、キュー（SplQueue）をスタック（SplStack）に変えれば、深さ優先探索になります。

データ出し入れのたびにソートしたい（SplMaxHeap）

データを出し入れするたびに、昇順や降順に並び替えたいことがあります。
たとえば、ABC368回のB問題 では、最大値と、次の最大値を1ずつ減らしていく操作が必要です。

このようなときは、ヒープ構造を、SplMaxHeapクラスで実装できます。
（この問題は降順なのでMaxHeapですが、昇順ならMinHeapが使えます）

<?php
// このコードはイメージなので、このままでは動きません
$heap = new SplMaxHeap();
$heap->insert('入力された配列の数字');
$a1 = $heap->extract();  // 最大値を取り出す
$a1 -= 1;
if ($a1 > 0){
    $heap->insert($a1);  // 処理後、条件を満たしていたら戻す
}

2進数にしたときの'1'を数えたい（gmp_popcount）

整数を2進数にして、その0と1の並びの中で、1だけを数えたいときがあります。
たとえば、ABC380回のD問題 では、（途中の検討は難しいので端折りますが）最終的に、2進数にしたときの1の数が、偶数か奇数かによって大文字になるか小文字になるかが変わります。

このようなときは、gmp_popcountという関数があります。

<?php
echo gmp_popcount(31);  // 5 2進数で 11111
echo gmp_popcount(32);  // 1 2進数で100000

ある数字よりも大きな素数を1つ取得したい（gmp_nextprime）

ある数字以上で最小の素数や、ある数字以下の素数を数列で欲しい場合があります。
たとえば、ABC383回のD問題では、ある数字以下の素数の配列をあらかじめ求められれば、それをfor文で繰り返すだけで答えが出ます。

このようなときは、gmp_nextprimeという関数があります。

<?php
$primes = [];  // ある数字以下の素数を格納する配列
$max = 100; // ある数字
$prime = 2;  // 一番小さい素数
while($prime < $max) {
    $primes[] = (int) $prime;
    $prime = gmp_nextprime($prime);
}
var_dump($primes);  // 100以下の素数、[2,3, ... ,97]が出力

2段階の比較をして並び替えたい(SplHeapの上書き)

並び替えのルールを変えたいこともあります。
これは、昨日開催されたABC384回のC問題なのですが、まず点数ごとに並び替えて、同点ならば名前の辞書順に並び替える必要があります。
つまり、点数は降順で、名前は昇順で並び替える必要があります。
このようなときは、SplHeap::compareというメソッドの上書きをすることで対応できます。

<?php
$data = [
    [100, 'C'],
    [200, 'B'],
    [100, 'A'],
];
class MyHeap extends \SplHeap {
    public function compare($value1, $value2):int {
        if ( $value1[0] === $value2[0] ) {
            return $value1[1] > $value2[1] ? -1 : 1;
        } else {
            return $value1[0] > $value2[0] ? 1 : -1;
        }
    }
}
$heap = new MyHeap();
foreach($data as $v) {
    $heap->insert($v);
}
foreach($heap as $v) {
    echo "({$v[0]}: {$v[1]})".PHP_EOL;
}
// 結果、点数降順で、名前辞書順に並び変わる
// (200: B)
// (100: A)
// (100: C)

なお、compareメソッドの上書きは、以前書いたSplPriorityQueueの記事でもやったことがあります。

他に、ユーザー定義のusortなどを使っても良いかもしれません。
また、他の方の回答を見ていると、array_multisort という関数を使っている方もいて、arrayの関数はとても奥が深いなぁと思いました。

なお、昨日のわたしの解法は、いずれも思い浮かばなかったので、愚直に場合分けしました。

PHPで失敗しやすいポイント

自分の書いたコードが、想像した通りに動いてくれないこともあります。
まず問題になるのが、配列の特殊性です。

arrayの特殊性

PHPマニュアルにもある通り、「PHPの配列は、実際には順番付けられたマップです。」
マップなので、定義されていない配列の範囲にも、代入可能です。（これは便利です）

<?php
$arr = [0, 1, 2];
$arr[100] = 3; // 代入可能

一方、この配列が、いろいろな問題も引き起こします。
よく指摘される問題は、array_filterです。

<?php
$evens = array_filter(range(0,9,1), fn($x)=>$x % 2 === 0);
echo $evens[1];
// $evensは、偶数だけフィルタされているから、[0,2,4,6,8]なので、
// 期待するもの: 2
// 実際: PHP Warning:  Undefined array key 1 ...

詳しくは、「PHPを使いもせずDISってる君達へ」が参考になります。

また、「PHPの最高機能、配列を捨てよう！！」にも、arrayの特殊性が紹介されており、参考になります。（YouTube もあります。）

とはいえ、実務でのデータのやり取りに配列を捨てるとしても、AtCoderでは配列を捨てる必要はありません。むしろどんどん使います。
競技プログラミングで書くコードは、その問題を解いている間（ビギナーコンテストならせいぜい100分間）だけ覚えておけばよいので、実務で使われるコードとは違うのでしょう。

SplFixedArray は、arrayより速くない

AtCoderにおいて、SPLのデータ構造（上記で紹介したSplQueueやSplHeapなど）は、とても便利なのですが、SplFixedArrayだけは、使いどころがありません。
通常のarrayと比べて、SplFixedArrayは、メモリの消費を節約できるようです。
しかし、時間の節約にはつながりません。
TLE（処理時間オーバー）したときに、SplFixedArrayで書き直しても、改善しないので注意が必要です。

以下のコードは、hrtimeを使って、arrayとSplFixedArrayの処理時間を比較したものです。

<?php
$number = 10 ** 7;
$len = intdiv($number, 2);
$start = 0;
$start = hrtime(true);  // arrayの計測開始
$a = [];
for($i = 0; $i < $number; $i++) {  // 配列を作る
    $a[$i] = $i * rand(1,2);
}
for($i = 0; $i < $len; $i++) {  // 順番を入れ替える
    $tmp = $a[$i];
    $a[$i] = $a[$number - 1 - $i];
    $a[$number - 1 - $i] = $tmp;
}
echo 'array: ';
echo intdiv(hrtime(true) - $start, 10 ** 6);
echo 'ミリ秒'.PHP_EOL;
$start = hrtime(true);  // FixedArrayの計測開始
$fa = new SplFixedArray($number);
for($i = 0; $i < $number; $i++) {  // 配列を作る
    $fa[$i] = $i * rand(1,2);
}
for($i = 0; $i < $len; $i++) {  // 順番を入れ替える
    $tmp = $fa[$i];
    $fa[$i] = $fa[$number - 1 - $i];
    $fa[$number - 1 - $i] = $tmp;
}
echo 'FixedArray: ';
echo intdiv(hrtime(true) - $start, 10 ** 6);
echo 'ミリ秒'.PHP_EOL;

// 結果
// array: 552ミリ秒
// FixedArray: 664ミリ秒

array_fill で new すると同じインスタンスが展開される

自作したクラスをarrayに格納して使いたい場面があります。
たとえば、ABC370回のD問題では、ボンバーマンみたいな世界で、縦横に爆破できる壁があるかどうかをチェックしていきます。

いろいろな解法があるとは思いますが、わたしは自作のUnionFindというクラスを、各行各列の配列に格納しようとしました。
ここで、ついつい array_fill(0,$n, new UnionFind()) と、したくなってしまうのですが、同じインスタンスが参照されてしまうようで、うまくいきません。

以下のコードは、この問題点を簡略化したものです。

<?php
class myClass {
    public array $arr = [0,1,2,3,4];
}
$myClasses = array_fill(0, 3, new myClass());  // myClassのインスタンスが3つ入っている配列を作っている
$myClasses[0]->arr[0] = 10;
echo $myClasses[1]->arr[0];
// $myClasses[0]のarrプロパティは、[10,1,2,3,4]に変更しているが、
// $myClasses[1]のarrプロパティには、変更を加えていないつもりなので、[0,1,2,3,4]が入っていると思っている。
// 期待するもの: 1
// 実際: 10

$myClassesには、myClassの別々のインスタンスが3つ入っていると思いがちですが、実際には、ひとつの同じインスタンスを参照しています。
myClassの配列が欲しい場合、素直にfor文にした方が良いようです。

感想

正直、AtCoderで競うだけなら、PHPでやる優位性は無いかもしれません。
C++の方が処理速度も早いですし、Pythonの方が解説記事も多いです。
一方で、これまで知らなかったPHPの関数や、ライブラリと出会う機会にはなっているなぁと思います。