トヨタ自動車プログラミングコンテスト2023＃4(AtCoder Beginner Contest 311)をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

A - First ABC

「Aが出現したか」「Bが出現したか」「Cが出現したか」のフラグ管理で解くことができます.

順番に全員が暇かを確かめていくことで解くことができます.

頂点$1$から$A_i$の指示にしたがって移動し続けていれば, いつかはサイクルに行き着くことになります.

サイクルに行き着いたかの判定は, 通った頂点を記録する列$S$に次の頂点が含まれるかで判定します. そして, $S$の要素のうち, 次の頂点が入っているインデックスから先を出力すればよいです.

サイクルの要素を順番に出力するために, $S$はlist()として記録しておく必要があります. しかし, $S$に次の頂点が含まれるかの判定をlist()でやっているとTLEとなってしまいます.

この問題は, $S$をset()としても記録しておき, $S$に次の頂点が含まれるかの判定をset()で行うことで解決できます.

到達可能なマスを幅優先探索(breadth first search; BFS)で調べていくことで解くことができます. プレイヤーは岩のマスにぶつかるまでその方向に移動することになるので, 止まった場所を記録しておく配列と通過した場所を記録しておく配列は別にしておくことがポイントです.

幅優先探索は以下でも取り上げています.

E以降は私の能力不足故に省略いたします.