Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

六村リオ / 霧島京子 / 緑川つばめ / 島根ルミ / 島根ルミ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点になってしまいクリアできませんでした。
理由がよくわからん。

rana_kualu
不労所得で生きたい。
https://twitter.com/rana_kualu
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした