warp (paizaランク B 相当)
下記の問題をプログラミングしてみよう！
paiza 君は 1 〜 N の番号がつけられた N マスを移動します。
移動のルールは次の通りです。
・i 回目の移動をマス x からおこなう場合、その移動先はマス to[x][i] となる。
to[x][i] が -1 の場合、現在のマスに移動してくる 1 つ前のマスが次の移動先となる。
paiza 君はマス 1 から移動を始めます。
マス 1 から K 回移動をしたとき、paiza 君が止まったマスの番号を止まった順に出力してください。
解答例(C++の場合を参考)
難易度が高くなっていますが、題意を正しく理解するのが難しいところに起因している気がします。問題文に以下のように書かれています。
to[x][i] が -1 の場合、現在のマスに移動してくる 1 つ前のマスが次の移動先となる。
この書き方ですと、移動先(to[x][i])が-1のとき、スタックの現在のマスはそのままに、移動先の１つ前のマスを新たにスタックに加えると解釈できます。
具体例を挙げれば、
訪れたマスを保持しておくスタックが[12, 15, 24]で、移動先-1の時、
現在のマスは24で、
１つ前のマスは15ですから、
スタックは[12, 15, 24, 15]、
移動後の現在のマスは15です。
さらに移動先が-1で、１つ前のマスに移動するとなった時、
現在のマスは15、
１つ前のマスは24ですから、
スタックは[12, 15, 24, 15, 24]、
移動後の現在のマスは24とです。
しかし、題意は違うようです。
模範解答のC++のコード例を見ると、
S.pop();//スタックの末尾(現在のマス)削除
now = S.top();//スタックの末尾(１つ前のマス)を取得
なので、スタックの現在のマスを削除し、移動先の１つ前のマスは加えない、となっています。
これは、"スタックの現在のマスを取り消して、1つ前のマスに戻る"ということです。
同じように、具体例を挙げれば、
訪れたマスを保持しておくスタックが[12, 15, 24]で移動先-1の時、
現在のマスは24で、
１つ前のマスは15ですから、
"現在のマスを取り消して、1つ前のマスに戻る"ので、
スタックは[12, 15]、(←ここが違う)
移動後の現在のマスは15、
とするようです。
さらに移動先が-1で、１つ前のマスに移動するとなった時、
現在のマスは15、
１つ前のマスは12ですから、(←ここが違う)
"現在のマスを取り消して、1つ前のマスに戻る"ので、
スタックは[12]、(←ここが違う)
移動後の現在のマスは12、(←ここが違う)
とするようです。
以上のように、2回続けて移動先が-1で１つ前のマスに移動するとなったときに、問題点が浮かび上がります。
１つ前のマスに移動するというのは、"新しい"１つ前のマスに移動することなのか、履歴の１つ前のマスに"戻る"ことなのか。
現在のマスの履歴を残して、"新しい"1つ前のマスに移動して、これも履歴を残すのか、
それとも、現在のマスの履歴を消して、元の１つ前のマスに移動して、"戻る"のか、
これがハッキリしません。
模範解答から推察するに、題意は、履歴の１つ前のマスに戻ることですので、現在のマスの履歴をスタックから削除することになります。
問題文からここまで読み取るのは難易度が高いなと感じました。
C++の模範解答をJavaScrptにしたものを載せておきます。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//マスの個数 N と移動する回数 K
const [N, K] = lines[0].split(" ").map(Number);
//移動元、現在のマス
let now = 0;
//移動先マスを表す二次元配列to、インデックスなので-1する
const to = lines.slice(1).map(line => line.split(" ").map(v => v = Number(v) - 1));
//移動先を記録するスタック
let S = [0];//初めのマスは1
//i回目の移動
for (let i = 0; i < K; i++) { //toのインデックスなので-1して0からK未満まで
if (to[now][i] === -2) {//移動先が-1なら
S.pop();//末尾(現在地)を取り出し
now = S[S.length - 1]; //一つ前に移動
} else {
now = to[now][i];//移動
S.push(now);//移動先を記録
}
//プレイヤーが止まるマスを順に改行区切りで出力
console.log(now + 1);
}
題意に沿わなかった解答例
移動先が-1のとき、新しい１つ前のマスに移動すると解釈して、現在のマスの履歴を残して、解答しました。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [N, K] = lines[0].split(" ").map(Number);
//移動先マスを表す二次元配列to
const to = lines.slice(1).map(line => line.split(" ").map(Number));
//移動先記録
let S = [1];//初めのマスは1
//i回目の移動
for (let i = 1; i <= K; i++) {
const x = S[i - 1];//現在のマス
if (to[x - 1][i - 1] === -1) { //移動先が-1の時
ans.push(S[i - 2]);//"新しい"現在のマスに移動してくる 1 つ前のマス
//現在のマスの履歴は削除しない
} else {
ans.push(to[x - 1][i - 1]);//移動先記録
}
}
//プレイヤーが止まるマスを順に改行区切りで出力
ans.shift();//初めの位置は取り除く
console.log(S.join("\n"));