🎄🎄🎄レバウェル開発部アドベントカレンダー19日目🎄🎄🎄
レバウェル開発部のJohnDoe1105と申します。
最近業務でPHPを使うチームに配属されたため、PHPへの慣れを兼ねてAtCoderに挑戦してみました。
取り組む対象の問題は、かの有名なAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～の記事の10選という記事で取り上げられている10問です。
これまで私は竸プロに取り組む際は専らPythonを利用していましたので、Pythonと比較した時のPHP特有の処理にフォーカスしてコードおよび感想を書いてみました。
※なお今回は言語仕様に慣れることを目的としてAtCoderに取り組むという趣旨の記事になるため、標準入出力の工夫やアルゴリズムそのもの、竸プロでスコアを上げるためのテクニックなどにフォーカスしたものはでない点、ご了承ください。
🔥過去問精選 10 問に取り組んでみた🔥
第 1 問: ABC 086 A - Product (100 点)
if文と偶奇判定の問題です。
これといってPHP特有の観点はないでしょう。
<?php
fscanf(STDIN, "%d %d", $a, $b);
if ($a % 2 && $b % 2) {
echo "Odd";
} else {
echo "Even";
}
第 2 問: ABC 081 A - Placing Marbles (100 点)
とてもシンプルな文字列走査の問題です。
Pythonとは大きく差が出る処理です。
PHPではデフォルトで文字列走査が手軽に出来る方法がないため、やや手間がかかります。
<?php
$line = fgets(STDIN);
$ans = 0;
foreach (preg_split('//u', $line, -1, PREG_SPLIT_NO_EMPTY) as $chr) {
if ($chr === "1") {
$ans++;
}
}
echo $ans;
第 3 問: ABC 081 B - Shift Only (200 点)
<?php
$n = fgets(STDIN);
$arr = explode(" ", fgets(STDIN));
$ans = 10000000000000;
foreach ($arr as $elm) {
$loop_ans = 0;
$elm = intval($elm);
while ($elm % 2 === 0) {
$elm /= 2;
$loop_ans += 1;
}
$ans = min($ans, $loop_ans);
}
echo $ans;
第 4 問: ABC 087 B - Coins (200 点)
for文をネストさせる全探索の問題です。
これといってPHP特有の処理はないでしょう。
<?php
$a = (int)fgets(STDIN);
$b = (int)fgets(STDIN);
$c = (int)fgets(STDIN);
$x = (int)fgets(STDIN);
$ans = 0;
for ($i = 0; $i <= $a; $i++) {
for ($j = 0; $j <= $b; $j++) {
for ($k = 0; $k <= $c; $k++) {
if ($i * 500 + $j * 100 + $k * 50 === $x) {
$ans++;
}
}
}
}
echo $ans;
第 5 問: ABC 083 B - Some Sums (200 点)
愚直な解き方だと文字列走査を行わせることになり、ミスを誘発します。
想定解のようにアルゴリズムを工夫すれば余計な処理を減らせる好例かもしれません。
<?php
fscanf(STDIN, "%d %d %d", $n, $a, $b);
$ans = 0;
$n = (int)$n;
for ($i = 1; $i <= $n; $i++) {
// 各桁の総和を求める
$ketasum = 0;
foreach (preg_split('//u', (string)$i, -1, PREG_SPLIT_NO_EMPTY) as $chr) {
$ketasum += (int)$chr;
}
if ($a <= $ketasum && $ketasum <= $b) {
$ans += $i;
}
}
echo $ans;
第 6 問: ABC 088 B - Card Game for Two (200 点)
降順ソートされた配列を用意する問題です。
PHPではarsort()を用います。
<?php
$n = (int)trim(fgets(STDIN));
$line = trim(fgets(STDIN));
$arr = explode(' ', $line);
arsort($arr);
$arr = array_values($arr);
$ans = 0;
foreach ($arr as $index => $elm) {
if ($index % 2 === 0) {
$ans += $elm;
} else {
$ans -= $elm;
}
}
echo $ans;
第 7 問: ABC 085 B - Kagami Mochi (200 点)
PHPではPythonと違い、set型がデフォルトで搭載されていないため、array_uniqueを用います。
<?php
$n = fgets(STDIN);
$arr = array();
while ($line = fgets(STDIN)) {
$arr[] = trim($line); // 空白や改行を除去
}
echo count(array_unique($arr));
第 8 問: ABC 085 C - Otoshidama (300 点)
これも第4問同様、for文をネストさせるだけのシンプルな全探索の問題です。
これといったポイントもないでしょう。
<?php
fscanf(STDIN, "%d %d", $n, $y);
for ($i = 0; $i <= $n; $i++) {
for ($j = 0; $j <= $n - $i; $j++) {
if ($i * 10000 + $j * 5000 + ($n - $i - $j) * 1000 === $y) {
echo "{$i} {$j} " . ($n - $i - $j);
return;
}
}
}
echo "-1 -1 -1";
第 9 問: ABC 049 C - Daydream (300 点)
アルゴリズム的な観点だと、逆順から処理をするという発想が出てこないとかなり苦戦する問題でしょう。
処理的な観点だと、「4つの文字列のどれかでdivideできるか」という処理を実装するのがやや面倒な問題です（筆者はこの実装に手こずりました）。
<?php
$s = trim(fgets(STDIN));
$sr = strrev($s);
// 逆順にした文字列について、残りが0文字になるまで判定を行う
while (strlen($sr)) {
// 文字列の残りが5文字未満の場合は不合格
if (strlen($sr) < 5) {
echo "NO";
return;
}
// 文字列の冒頭5文字か6文字について、パターンに合致するか判断
if (in_array(substr($sr, 0, 5), ["maerd", "esare"])) {
$sr = substr($sr, 5);
continue;
} elseif (in_array(substr($sr, 0, 6), ["resare"])) {
$sr = substr($sr, 6);
continue;
} elseif (in_array(substr($sr, 0, 7), ["remaerd"])) {
$sr = substr($sr, 7);
continue;
}
// continueされなかった場合は不合格
echo "NO";
return;
}
// ループをreturnせず抜けた場合は答えを出力
echo "YES";
第 10 問: ABC 086 C - Traveling (300 点)
アルゴリズムの観点以外だと、これといった特徴はない問題です。
<?php
$n = trim(fgets(STDIN));
$x1 = 0;
$y1 = 0;
$t1 = 0;
for ($i = 1; $i <= $n; $i++) {
fscanf(STDIN, "%d %d %d", $t2, $x2, $y2);
$base = abs($t1 - $t2) - (abs($x1 - $x2) + abs($y1 - $y2));
if ($base >= 0 && $base % 2 === 0) {
$x1 = $x2;
$y1 = $y2;
$t1 = $t2;
continue;
}
echo "No";
return;
}
echo "Yes";
感想
数年ぶりにAtCoderに取り組んでみました。
以前Pythonで取り組んでいた際は、シンプルに処理が記述できていた記憶があったのに加え、ネット上の情報も豊富だったため、PHPでの取り組みはやや苦戦しました。
良い頭の体操になると共に、時間を割いて取り組んでいた学生時代とはAtCoderに対する見方がかなり変わったように感じます。
機会があれば記事にしたいと思いますが、ポエム色が強くなりそうなのでこの記事では控え、また別の機会に筆を執ることとします。
参考にさせていただいたリンク
今回の記事を書くうえで参考にさせていただいたリンクです。