慶應SFC　総合政策学部　情報入試　2019年　大問Ⅴ　過去問解説

この問題には4つの解が存在する。

解1

(ア)

まずだが、これは
・等しいならば「到達不可能」と出力する
・途中で更新されている
ことから
i番目の配置の集合
であると分かる。
したがっては{s}である。

処理Aが始まった段階ではiが1増えたばかりで今の配置は分かっていない。
したがってを空集合とする。(※1)
そしての各要素に対して次に動かしたときにどうなるか処理を行う。(※2)

の候補はの各要素である。

途中で変数の値をとすればよい。

にはi番目の配置の集合が入っているから、これが空集合となった場合は到達不可能である。(※3)

(イ)
Zはすでに探索した配置の集合。
2回以上探索しないようにZを用いたアルゴリズムを組み込んでいる。

(ウ)
gに到達可能なsから始めた場合は、処理Cでq=gになることはあるから、時間はかかるかもしれないが正しい結果は得られる。
gに到達不可能なsから始めた場合は、に必ずqを追加してしまうから、が空集合にならず無限に繰り返し実行される。(※4)

解2

解1の※1でを{s}としても解1は成り立つ。
その場合、※3も{s}となった場合としなくてはいけない。
なぜなら、は{s}であり、Zの存在によりi≧1の場合のにs以外の既に探索したものが入ることはないからである。

解3

解1の※1でをとしても解1は成り立つ。
その場合、※3もとなった場合としなくてはいけない。
理由は解2と同じ。
そしてこのとき、※4が変わる。
gに到達不可能なsから始めた場合でも、Zの存在によりに以前のものしか入っていなかったら、もう変更は不可能だと判断できる。
よって時間はかかるかもしれないが正しい結果は得られる。

解4

解3の場合で、※2を
そしての各要素に対してどうなっているか処理を行う
としても解3は成り立つ。
にはあらかじめが入っているにすぎない、と見做せるからである。