POH6 漫画版: 女子高生プログラマーの大バトル！〜コボール文明の逆襲〜 霧島京子

六村リオ / 霧島京子 / 緑川つばめ / 島根ルミ / 島根ルミ149 / 島根ルミ121 / 共通解

すごろくを解きます。
先に攻略可不可リストを作っておいて、答えはそのリストを参照するだけ、という回答方針。

<?php
	// インプット
	$f = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
	
	// ゴール可能かリスト -2は未判定、-1は判定中、1は可能、0は不可能
	$isok = array_fill(0, array_shift($f)-1, -2);
	$isok[0] = 0; // スタート
	$isok[] = 1; // ゴール
	// すごろく
	$list = explode(' ', array_shift($f));
	// 3行目は要らない
	unset($f[0]);
	
	// 攻略可能か全項目調査
	foreach($list as $k=>$v){
		$isok[$k] = checkRecursive($k, $list, $isok);
	}
	
	// 4行目以降でループ
	foreach($f as $k=>$v){
		echo $isok[$v] ? "Yes\n" : "No\n";
	}
	
	/**
	 * ゴールできるかどうかを調べて返す。
	 * @param int 現在のキー
	 * @param [] すごろく
	 * @param [] OKリスト
	 * @return int 1は可能、0は不可能
	 */
	function checkRecursive($k, $list, $isok){
		// 範囲外
		if(!isset($isok[$k])){return 0;}
		// 既に決定している
		if($isok[$k] >= 0){return $isok[$k];}
		// 調査中だったらループしたので失敗
		if($isok[$k] === -1){return 0;}
		// それ以外は、自分を調査中にして次のキーへ
		$isok[$k] = -1;
		return checkRecursive($k+$list[$k], $list, $isok);
	}

https://paiza.jp/poh/joshibato/kirishima/result/b60a23dc
問題なく100点。

ただ、時間的には全く問題ないとはいえ、これだと同じ場所を何度もチェックすることになります。
そこでcheckRecursiveの引数$isokを参照渡しにしてメモ化すればもっと早くなると思ったんだけど、そうするとテストは通るのに本番が0点になってしまいクリアできませんでした。
理由がよくわからん。