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点になってしまいクリアできませんでした。
理由がよくわからん。