【PHP】AtCoder Beginners Selectionを解いてみた

はじめに

AtCoder Beginners Selection をPHPで解いてみました。PHPでAtCoderを始めてみたいという方のご参考になれば幸いです。

標準入力・標準出力とテンプレートについては以下の記事で解説しています。ソースコードはすべてこのテンプレートを使用して作成していますのでご了承ください。

第1問：ABC086A - Product

問題

二つの正整数 $a,b$ があります。$a$ と $b$ の積が偶数なら Even 、奇数なら Odd を出力してください。

• $1 \le a,b \le 10000$
• 入力はすべて整数

解法

ある整数が「偶数である」とは「 $2$ の倍数である」と言い換えることができます。よって、$a$ と $b$ の積が $2$ の倍数かどうかを判別する 倍数判定 ができれば、この問題を解くことができそうです。

倍数判定は余りに着目します。整数 $n,m$ に対して、$n$ を $m$ で割ったときの余りが $0$ であるとき、$n$ を $m$ の倍数であるといいます。例えば、$12$ を $2$ で割ったときの余りは $0$ なので、$12$ は $2$ の倍数です。また、余りは二項演算子 % で求めることができます。よって、以下のような条件分岐によって Even か Odd を出力することで問題を解くことができました。

• (a * b) % 2 === 0 が成り立つなら偶数なので Even を出力
• (a * b) % 2 !== 0 が成り立つなら奇数なので Odd を出力（条件式を書かずに else でも大丈夫です）

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($a, $b) = ints();

	// 積が偶数の場合
	if (($a * $b) % 2 === 0) {
		output('Even');
	}
	// 積が奇数の場合
	else {
		output('Odd');
	}
}

main();

補足

余りに関連するものとして、整数同士を割り算をしたときの小数部の切り捨て・切り上げについても説明します。PHPの割り算は答えが割り切れないとき、その答えが浮動小数点数型に変換されます。そのため、小数部の切り捨て・切り上げをしたい場合は以下のようにします。

<?php

$a = 7;
$b = 2;

$ans1 = intdiv($a, $b);          // 切り捨て
$ans2 = intdiv($a + $b - 1, $b); // 切り上げ

var_dump($ans1); // int(3)
var_dump($ans2); // int(4)

intdiv 関数は第1引数に割られる数、第2引数に割る数を指定することで、割り算の結果を小数部切り捨てで取得できます。特に、(a + b - 1) / b で小数部を切り上げる計算方法は典型テクニックですので、覚えておくと役立つと思います。

また、似たようなことができる関数として floor 関数と ceil 関数というものがあります。しかし、これらの関数は個人的には 非推奨 です。なぜなら、計算過程で浮動小数点数型が登場するため、誤差によって意図しない答えが返ってくる可能性があるからです。

第2問：ABC081A - Placing Marbles

問題

$1,2,3$ の番号がついた $3$ つのマスがあります。
各マスには 0 か 1 が書かれており、マス $i\ $には $s_i$ が書かれています。
1 が書かれたマスがいくつあるか求めてください。

• $s_1,s_2,s_3$ は 1 あるいは 0

解法

$s_1,s_2,s_3$ の値をすべて確認して、1 の個数を数え上げればよさそうです。このようにすべての値を確認する方法を 全探索 といいます。全探索は競プロにおいて最も基本的なアルゴリズムの一つです。

さて、$s_1,s_2,s_3$ の値を確認するためには、文字列の $i$ 番目の値を取得する必要があります。そのためには以下のようにすればよいです。

<?php

$s = 'apple';

var_dump($s[0]); // string(1) "a"
var_dump($s[1]); // string(1) "p"
var_dump($s[2]); // string(1) "p"
var_dump($s[3]); // string(1) "l"
var_dump($s[4]); // string(1) "e"

文字列が入れられた変数に [0] のように添え字をつけることで、その文字列の $i\ $番目の値を取得することができます。ただし、添え字は $0$ から始まる 0-indexed であることに注意が必要です。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($s) = strings();

	// 1が書かれたマスの個数
	$ans = 0;

	// 全探索
	for ($i = 0; $i < 3; ++$i) {
		// s_iが1なら
		if ($s[$i] === '1') {
			// 1が書かれたマスの個数を+1する
			++$ans;
		}
	}

	// 出力
	output($ans);
}

main();

補足

文字列型は foreach 文でループさせることができないので注意が必要です。そのため、文字列の長さを取得する strlen 関数を用いて以下のように書くことになります。

<?php

$s = 'apple';

for ($i = 0; $i < strlen($s); ++$i) {
	var_dump($s[$i]); // a,p,p,l,eの順に出力される
}

どうしても foreach 文でループさせたいという人向けに、文字列を1文字ずつ分割した配列にする str_split 関数を用いて以下のように書くこともできます。（無駄にメモリを食うのでオススメはしません。）

<?php

$s = 'apple';

foreach (str_split($s) as $v) {
	var_dump($v); // a,p,p,l,eの順に出力される
}

他にも文字列に関する性質、便利な関数などがいくつかありますので、それについてもまとめておきます。

• 文字列の結合：文字列と文字列の間を . でつなぐことで結合できます
• 文字の書き換え：添え字を指定することで、取得だけでなく書き換えも可能です
• 文字列の大小関係の比較：二項演算子 > < >= <= で辞書順の比較ができます
• 部分文字列：substr 関数
• 繰り返し文字列：str_repeat 関数
• 文字列の反転：strrev 関数
• a～z の配列作成：range 関数を用いて、range('a', 'z');
• 文字列の置換：対象全てを置換するなら str_replace 関数、置換回数に指定があるなら preg_replace 関数

第3問：ABC081B - Shift only

問題

黒板に $N$ 個の正の整数 $A_1,...,A_N$ が書かれています。
黒板に書かれている整数がすべて偶数であるとき、次の操作を行うことができます。

• 黒板に書かれている整数すべてを、$2$ で割ったものに置き換える。

最大で何回操作を行うことができるかを求めてください。

• $1 \le N \le 200$
• $1 \le A_i \le 10^9$ $(1 \le i \le N)$
• 入力はすべて整数

解法

問題文の操作を愚直に シミュレーション すると以下のようなループになります。

• 黒板に書かれている整数がすべて偶数かを判定
• 奇数があればループを抜ける
• 黒板に書かれている整数すべてを、$2$ で割ったものに置き換える
• 操作した回数を ＋$1$ する

「奇数があればループを抜ける」処理は奇数があるかどうかをフラグで管理すればよさそうです。ただし、フラグの管理の仕方は大きく分けて $2$ 種類存在し、そのどちらで実装するかを判断する必要があります。

• 少なくとも一つ条件を満たすものが存在するかの判別：フラグを false で初期化して、条件を満たすものがあれば true に更新する
• すべてのものが条件を満たしているかの判別：フラグを true で初期化して、条件を満たさないものがあれば false に更新

「奇数があれば」ということは「少なくとも一つ奇数が存在する」と言い換えることができますので、前者の方法でフラグ管理をしていきます。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n) = ints();
	$a = ints();

	// 操作の回数
	$ans = 0;

	// 可能な限り操作を繰り返す
	while (true) {

		// 奇数が存在するか
		$odd_exists = false;

		// 奇数が存在するか確認
		for ($i = 0; $i < $n; ++$i) {
			if ($a[$i] % 2 === 1) {
				$odd_exists = true;
			}
		}

		// 奇数が存在するなら
		if ($odd_exists) {
			break;
		}

		// 2で割ったものに置き換える
		for ($i = 0; $i < $n; ++$i) {
			$a[$i] = intdiv($a[$i], 2);
		}

		// 操作の回数を+1する
		++$ans;
	}

	// 出力
	output($ans);
}

main();

補足

フラグ管理をせずに、break 2; で for 文と while 文の両方から抜ける方法もあります。

第4問：ABC087B - Coins

問題

$500$ 円玉を $A$ 枚、$100$ 円玉を $B$ 枚、$50$ 円玉を $C$ 枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りありますか。
ただし、同じ種類の硬貨は区別することができません。

• $0 \le A,B,C \le 50$
• $A+B+C \ge 1$
• $50 \le X \le 20000\ $
• $A,B,C$ は整数
• $X$ は $50$ の倍数

解法

計算でごちゃごちゃやるのは少し大変です。そのため、ありうる硬貨の枚数の組み合わせを 全列挙 する方法を考えます。今回は以下の $3$ 種類の硬貨の組み合わせを列挙すればよさそうです。

• $500$ 円玉：$0$ ～ $A$ 枚
• $100$ 円玉：$0$ ～ $B$ 枚
• $50$ 円玉：$0$ ～ $C$ 枚

組み合わせの列挙は for 文のネストを増やすことで実装することができます。つまり、$500$ 円玉の枚数分の for 文、$100$ 円玉の枚数分の for 文、$50$ 円玉の枚数分の for 文の $3$ つがネストされたループを実装すればよいです。あとは、各硬貨の枚数の組み合わせのうち、合計金額がちょうど $X$ 円になるものを数え上げることで、問題を解くことができました。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($a) = ints();
	list($b) = ints();
	list($c) = ints();
	list($x) = ints();

	// 条件を満たす組み合わせの数
	$ans = 0;

	// 500円玉の枚数
	for ($i = 0; $i <= $a; ++$i) {
		// 100円玉の枚数
		for ($j = 0; $j <= $b; ++$j) {
			// 50円玉の枚数
			for ($k = 0; $k <= $c; ++$k) {
				// 合計金額がちょうどX円なら
				if (500 * $i + 100 * $j + 50 * $k === $x) {
					// 組み合わせの数を+1する
					++$ans;
				}
			}
		}
	}

	// 出力
	output($ans);
}

main();

第5問：ABC083B - Some Sums

問題

$1$ 以上 $N$ 以下の整数のうち、$10$ 進法での各桁の和が $A$ 以上 $B$ 以下であるものの総和を求めてください。

• $1 \le N \le 10^4$
• $1 \le A \le B \le 36$
• 入力はすべて整数

解法

整数の各桁は、求めたい桁が $1$ 桁目であるような整数を用意して $10$ で割った余りを計算して求めることができます。例えば、$314$ の各桁を求める場合は以下のようになります。

• $1$ 桁目：$314$ を $10$ で割った余りを計算して $4$
• $2$ 桁目：$31$ を $10$ で割った余りを計算して $1$
• $3$ 桁目：$3$ を $10$ で割った余りを計算して $3$

$31$ は $314$ を $10$ で割って小数部を切り捨てることで求められます。また、$3$ は $31$ を $10$ で割って小数部を切り捨てることで求められます。よって、以下のようなループを記述すればよさそうです。

• $x \le 0\ $ ならループを抜ける
• $x$ を $10$ で割った余りを求める
• $x$ を、$x$ を $10$ で割って小数部を切り捨てた数で更新する

あとは、$1$ 以上 $N$ 以下の整数に対して、各桁の和が $A$ 以上 $B$ 以下であるかを判定してその総和を求めればよいです。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n, $a, $b) = ints();

	// 条件を満たす整数の総和
	$ans = 0;

	// 1以上N以下の整数
	for ($num = 1; $num <= $n; ++$num) {

		$x   = $num; // $numは更新できないので$xを更新していく
		$sum = 0;    // 各桁の和

		// $xが0になるまで
		while ($x > 0) {
			$sum += $x % 10;     // ある桁の数を足す
			$x = intdiv($x, 10); // $xを10で割って小数部を切り捨て
		}

		// 各桁の和がA以上B以下なら
		if ($a <= $sum && $sum <= $b) {
			$ans += $num; // 条件を満たした整数を加算
		}
	}

	// 出力
	output($ans);
}

main();

第6問：ABC088B - Card Game for Two

問題

$N$ 枚のカードがあります。$i$ 枚目のカードには $a_i$ という数が書かれています。
Alice と Bob は、これらのカードを使ってゲームを行います。ゲームでは、Alice と Bob が交互に $1$ 枚ずつカードを取っていきます。先にカードを取るのは Alice です。
$2$ 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。$2$ 人とも自分の得点を最大化するように最適な戦略を取った時、Alice は Bob より何点多く取るか求めてください。

• $1 \le N \le 100$
• $1 \le a_i \le 100$ $(1 \le i \le N)$
• 入力はすべて整数

解法

まず、「最適な戦略」について考えていきます。このゲームは取ったカードの数の合計がその人の得点になります。$2$ 人とも自分の得点を最大化するようにカードを取るため、数が大きいカードから順に取るのが最適な戦略と言えそうです。

数が大きい順にカードを選ぶためには、$a$ を ソート しておくと実装が楽になります。あとは、0-indexed で偶数番目なら Alice の得点、奇数番目なら Bob の得点となるように得点の合計を管理し、その差分を出力することで問題を解くことができました。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n) = ints();
	$a = ints();

	// 降順にソート
	rsort($a);

	$alice = 0; // Aliceの得点の合計
	$bob   = 0; // Bobの得点の合計

	// a_iが書かれたカードを取っていく
	for ($i = 0; $i < $n; ++$i) {

		// 偶数番目なら
		if ($i % 2 === 0) {
			$alice += $a[$i]; // Aliceに得点を加算
		}
		// 奇数番目なら
		else {
			$bob += $a[$i]; // Bobに得点を加算
		}
	}

	// AliceとBobの得点の差分が答え
	$ans = $alice - $bob;

	// 出力
	output($ans);
}

main();

補足

PHPのソート関数は種類がたくさんありますが、sort と rsort さえ使いこなせれば十分戦えます。あとは必要に応じて調べて使うのがよいと思います。

第7問：ABC085B - Kagami Mochi

問題

$X$ 段重ねの鏡餅 $(X \ge 1)$ を作ります。$X$ 段重ねの鏡餅とは、$X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。
$N$ 枚の円形の餅があります。$i$ 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるか求めてください。

• $1 \le N \le 100$
• $1 \le d_i \le 100$
• 入力はすべて整数

解法

直径の大きな鏡餅を下から順に積み重ねていけばよさそうです。ここで、直径が同じ鏡餅どうしを縦に積み重ねることができない点に注意する必要があります。そのため、直径が同じ餅を $1$ つだけ残して取り除き、残った餅で作る鏡餅が最大になります。

配列の重複分を削除するには array_unique 関数を使用するとよいです。あとは、重複後の配列の要素数が答えとなるため、この問題を解くことができました。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n) = ints();
	$d = [];
	for ($i = 0; $i < $n; ++$i) {
		list($d[]) = ints();
	}

	// 重複分を取り除いた配列
	$d_unique = array_unique($d);

	// 最大の鏡餅の段数
	$ans = count($d_unique);

	// 出力
	output($ans);
}

main();

第8問：ABC085C - Otoshidama

問題

$10000$ 円札、$5000$ 円札、$1000$ 円札のことを「お札」と呼びます。お年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。そうでない場合は -1 -1 -1 を出力してください。

• $1 \le N \le 2000$
• $1000 \le Y \le 2×10^7$
• $N$ は整数
• $Y$ は $1000$ の倍数

解法

まずは、第4問：ABC087B - Coins のように、$10000$ 円札、$5000$ 円札、$1000$ 円札の枚数の組み合わせを列挙する方法を考えます。

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n, $y) = ints();

	// お年玉の組み合わせを全列挙
	for($a = 0; $a <= $n; ++$a) {
		for ($b = 0; $b <= $n; ++$b) {
			for ($c = 0; $c <= $n; ++$c) {

				$m   = $a + $b + $c;                       // 枚数
				$sum = $a * 10000 + $b * 5000 + $c * 1000; // 金額

				// 枚数が同じ かつ 金額が同じ なら
				if ($n === $m && $sum === $y) {
					output($a, $b, $c); // 出力
					return;             // 処理終了
				}
			}
		}
	}

	// 条件を満たすお年玉の組み合わせがなかった場合の出力
	output(-1, -1, -1);
}

main();

しかし、これではこの問題に正答することはできません。なぜなら列挙する組み合わせの数が $(N+1)^3$ となり、実行時間制限を超えてしまうからです。$1 \le N \le 2000\ $ より、$N$ は最大で $2000$ となるので、for 文のループ回数はざっくり $N^3=2000^3=8×10^9$ となってしまいます。$1$ 秒間に処理できる for 文のループ回数は $10^8$ 程度なので、何らかの工夫が必要そうです。

計算回数を減らすコツは「こうだったらいいのになあ」とループ回数を決め打つことです。たとえば、「$N^3$ ではなく $N^2$ だったらいいのになあ」と決め打ち、そこからどのように実装をすればよいかを考えていきます。$N^2$ であれば、$N^2=2000^2=4×10^6$ となり、実行時間制限に間に合いそうです。

$N^2$ なので $2$ 回までは for 文を回せます。つまり、$10000$ 円札と $5000$ 円札の組み合わせは列挙して、$1000$ 円札の枚数はループを回さずに求められないか考えます。ここで、$10000$ 円札、$5000$ 円札、$1000$ 円札の枚数を $A,B,C$ とすると、$A+B+C=N$ より $C=N-A-B$ となり $1000$ 円札の枚数が計算で求められることがわかります。よって、$3$ 回目の for 文を回すことなく、$2$ 回の for 文で実装することができました。あとは、その組み合わせにおけるお札の合計金額が $Y$ と一致するかを判定していけばよいです。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n, $y) = ints();

	// お年玉の組み合わせを全列挙
	for($a = 0; $a <= $n; ++$a) {
		for ($b = 0; $a + $b <= $n; ++$b) {

			$c   = $n - $a - $b;                       // 1000円札の枚数
			$sum = $a * 10000 + $b * 5000 + $c * 1000; // 金額

			// 金額が同じなら
			if ($sum === $y) {
				output($a, $b, $c); // 出力
				return;             // 処理終了
			}
		}
	}

	// 条件を満たすお年玉の組み合わせがなかった場合の出力
	output(-1, -1, -1);
}

main();

補足

「$1$ 秒間に処理できる for 文のループ回数は $10^8$ 程度」と書きましたが、PHPの場合は速度が遅いので大体 $10^7$ 程度です。これは自分の体感ですが、実行時間制限が $2$ 秒のときは大体以下のようになっていると思います。

• $5×10^6$：大体間に合う
• $1×10^7$：ギリギリ間に合う
• $5×10^7$：間に合わないことが多い
• $1×10^8$：ほとんど間に合わない

第9問：ABC049C - 白昼夢

問題

英小文字からなる文字列 $S$ が与えられます。$T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。

• $T$ の末尾に dream dreamer erase eraser のいずれかを追加する。
  　
• $1 \le |S| \le 10^5$
• $S$ は英小文字からなる

解法

$S$ を先頭から見ていって、dream dreamer erase eraser が現れたらその文字列を $T$ に追加すればよさそうです。しかし、$S$ が「dreamer...」となっているときに、

• dream+erase
• dream+eraser
• dreamer

のどれになるかはその後ろの文字列を見に行かないとわかりません。つまり、dream と erase が出てきたときにそこで打ち切ってよいのか、後ろを見て dreamer か eraser にするのかを判別しないといけないところが難しいポイントです。

そこで、考察のカギになるのは「こうだったらいいのになあ」です。例えば、$T$ に追加できる文字が apple banana orange grape だった場合、$S=T$ にできるかの判別がとても楽になります。$S$ が「apple...」となっているとき、誰がどう見ても apple を追加すればよいことが一目でわかります。この違いは、どの文字列を追加したらよいかが、その後ろを見に行かなくても判別できる 点です。

さて、なぜこのような考察をしたかというと、この問題を先ほどの考察に帰着させたいからです。ここで、考察の典型テクニックとして 「逆を考える」 というものがあります。どういうことかというと、この問題において「逆を考える」と以下のような言い換えができます。

• 言い換え前：$T$ の末尾に dream dreamer erase eraser のいずれかを追加する。
• 言い換え後：$T$ の末尾に maerd remaerd esare resare のいずれかを追加する。（ただし、$S$ も逆順にする。）

このようにすることで、maerd remaerd esare resare のどれが $S$ に出現してもそこで打ち切って問題ないことがわかります。つまり、$S$ を逆順から見ていくことによって、先ほどの考察に帰着させることができました。あとは、$S$ の部分文字列を見ていき、すべて maerd remaerd esare resare に置き換えが可能かを確認していけばよいです。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($s) = strings();

	// Sを逆順にする
	$s = strrev($s);

	// Tに追加できる文字列
	$add_str_list = [
		strrev('dream'),
		strrev('dreamer'),
		strrev('erase'),
		strrev('eraser'),
	];

	$t = '';       // Tの文字列
	$sub_str = ''; // Sの部分文字列

	for ($i = 0; $i < strlen($s); ++$i) {
		// Sの部分文字列に現在の文字を追加
		$sub_str .= $s[$i];
		foreach ($add_str_list as $add_str) {
			// Sの部分文字列とTに追加できる文字列が一致していれば
			if ($sub_str === $add_str) {
				$t .= $add_str; // Tに文字列を追加
				$sub_str = '';  // 次の部分文字列を見に行くため空にする
			}
		}
	}

	// 出力
	if ($s === $t) {
		output('YES');
	}
	else {
		output('NO');
	}
}

main();

第10問：ABC086C - Traveling

問題

二次元平面上を移動していくことを考えます。時刻 $0$ のとき、点 $(0,0)$ にいます。時刻 $t$ に点 $(x, y)\ $ にいる時、時刻 $t+1$ には点 $(x+1, y), (x-1, y), (x, y+1), (x, y-1)$ のうちいずれかに存在することができます。その場にとどまることはできません。$1$ 以上 $N$ 以下の各 $i\ $ に対し、時刻 $t_i$ に点 $(x_i, y_i)$ を訪れます。この計画が実行可能かどうか判定してください。

• $1 \le N \le 10^5$
• $0 \le x_i \le 10^5$
• $0 \le y_i \le 10^5\ $
• $1 \le t_i \le 10^5\ $
• $t_i < t_{i+1}$ $(1 \le i \le N-1)$
• 入力はすべて整数

解法

$(x_i,y_i)$ から $(x_{i+1},y_{i+1})$ までの距離を $dist = |x_{i+1}-x_i|+|y_{i+1}-y_i|$、時刻の差を $dt = t_{i+1} - t_i$ とします。

まず、$(x_i,y_i)$ から $(x_{i+1},y_{i+1})$ に移動するためには、少なくとも $dist$ 秒は必要です。よって、$dt < dist\ $ の場合は、時刻 $t_{i+1}$ に $(x_{i+1},y_{i+1})\ $ を訪れることができません。

次に、$dt \ge dist\ $ の場合を考えます。結論から述べると、$dt - dist\ $ が偶数の場合は時刻 $t_{i+1}$ に $(x_{i+1},y_{i+1})$ を訪れることができて、奇数の場合はできません。

最短距離で $(x_{i+1},y_{i+1})$ に移動した場合、$dt - dist$ 秒だけ早く到着してしまいます。そのため、$(x_{i+1},y_{i+1})$ 付近でウロウロして時刻 $t_{i+1}$ になるのを待つ必要があります。そのとき、待ち時間が偶数秒のときは、$(x_{i+1},y_{i+1})$ にいることができ、奇数秒のときは別の場所にいることになります。このように、偶奇に着目 することは考察の典型テクニックの一つです。よって、以下のように $1 \le i \le N$ の地点について条件判定をし、適切にフラグ管理をすることで、この問題を解くことができました。

• 時間が足りない場合（ $dt < dist$ ）
  • 到達できない…
• 時間が足りる場合（ $dt \ge dist$ ）
  • 到達後の残り時間が偶数の場合（ $\hspace{0.1ex} dt - dist$ が偶数 ）
    • 到達できる！
  • 到達後の残り時間が奇数の場合（ $\hspace{0.1ex} dt - dist$ が奇数 ）
    • 到達できない…

※実装ではもう少しシンプルにまとめています。

サンプルコード

<?php

function strings() { return explode(' ', trim(fgets(STDIN))); }
function ints() { return array_map('intval', strings()); }
function doubles() { return array_map('doubleval', strings()); }
function output(...$args) { echo implode(' ', $args), "\n"; }

function main() {

	// 入力
	list($n) = ints();
	// 時刻0のとき(0,0)にいることを追加すると実装が楽
	$t = [0];
	$x = [0];
	$y = [0];
	for ($i = 0; $i < $n; ++$i) {
		list($t[], $x[], $y[]) = ints();
	}

	$is_ok = true; // 計画が実行可能かどうか

	for ($i = 0; $i < $n; ++$i) {
		$dist = abs($x[$i + 1] - $x[$i]) + abs($y[$i + 1] - $y[$i]); // 距離
		$dt   = $t[$i + 1] - $t[$i];                                 // 時刻の差

		// 時間が足りない場合 または 到達後の残り時間が奇数の場合
		if ($dt < $dist || ($dt - $dist) % 2 === 1) {
			$is_ok = false;
		}
	}

	// 出力
	if ($is_ok) {
		output('Yes');
	}
	else {
		output('No');
	}
}

main();

まとめ

• 第1問：ABC086A - Product
  • 倍数判定 は余りに着目
  • 切り捨て除算は intdiv($a, $b)
  • 切り上げ除算は intdiv($a + $b - 1, $b)
• 第2問：ABC081A - Placing Marbles
  • 競プロの基本は 全探索
  • 文字列は添え字を指定して $i\ $番目の文字を取得可能
• 第3問：ABC081B - Shift only
  • 問題文の操作をそのまま実装する方法は シミュレーション
  • 「少なくとも一つ条件を満たす」か「すべてのものが条件を満たす」かでフラグの持ち方が変わる
• 第4問：ABC087B - Coins
  • 組み合わせを全パターン試す方法は 全列挙
  • 全列挙は for 文のネスト構造で実装可能
• 第5問：ABC083B - Some Sums
  • 整数の各桁を求めるには「$10$ で割った余りを計算」と「$10$ で割った値で更新」を繰り返す
• 第6問：ABC088B - Card Game for Two
  • 「大きい順」または「小さい順」は ソート
• 第7問：ABC085B - Kagami Mochi
  • 配列の重複削除は array_unique 関数
• 第8問：ABC085C - Otoshidama
  • $1$ 秒間に処理できる for 文のループ回数は $10^8$ 程度（PHPだと $10^7$ 程度）
  • 計算回数を減らすコツは、ループ回数を決め打ってから実装可能かを考えること
• 第9問：ABC049C - 白昼夢
  • 「逆を考える」 ことで簡単な問題に帰着できることがある（考察の典型テクニック）
• 第10問：ABC086C - Traveling
  • 「偶奇に着目」 も考察の典型テクニック