ARC056 B - 駐車場
解法
珍しく探索問題です。
番目の人が駐車するには、スタート地点から頂点
へ向かう、次の条件を満たすルートが存在します。
- スタート地点を含む、通り道に存在する頂点の番号すべてが
より大きい
ということで、基本的には幅優先を行い、今いる頂点と同時に、通った頂点の番号の最小値をセットで記録しておきます。すると、その最小値よりも次に通る頂点の番号が小さい時、その次に通る頂点では駐車をすることができます。
これを効率よく探索するには、あるルートを通ったときの通る頂点の最小値をとしたとき、
番目の頂点にたどり着くようなルートについての
のうち、最大のもののみを調べればよいです。
にたどり着くようなルートが例えば2つ存在し、それぞれの
を
と
(
)とすると、
についての、
より先の探索は、
について探索した結果にすべて含まれます。ので、大きい方のみを探索すればいいです。これは現在の
の最大値をそれぞれの頂点に対して記録しておくことで、かなり高速化できます。今見ているルートについての
が、すでに探索を終えている現状の最大値
より大きければ探索を続行、そうでなければ打ち切りをします。
そして、仮にある頂点で駐車できなかったとしても、それより先で駐車できる可能性が存在するので、探索を打ち切らないようにすることも注意が必要です。
あとは、幅優先探索を行うことで、十分な速度で答えを求めることができます。
