ABC223 参加記録 - geam1113’s diary

コンテスト中AC:A〜D

左端と右端の導火線のうち、燃え尽きる時間が早い方を燃え尽きさせ、そのかかった時間分、もう一方の導火線を短くすることを繰り返す。その際、左から進んだ距離を合計しておく。最後に、導火線が一本になったら、残った長さの半分が最後に左から進む距離となるので、距離の合計に足す。

というものです。

トポロジカルソートによって解ける問題です。

$A_i$ から $B_i$ に向かう有向辺があるグラフとみなします。

閉路が存在する場合(DAGでない場合)、該当の $P$ は存在しないため、-1です。トポロジカルカルソートで判定可能です。

トポロジカルソートでは入次数が0になった頂点を一旦保存する処理がありますが、辞書順最小にするために順序付きの集合で管理します。

C++ならsetやpriority_queueです。

追加可能な数の集合があったとき、そこから辞書順最小の文字をとって $P$ の末尾に追加すれば、以降これより辞書順が小さくなることはありません。

トポロジカルソートは $O(N+M)$ なので、値の追加・取得・削除が $O(logN)$ として、 $O((N+M)logN)$ かと思います。

コンテスト中最初は、何故か逆向きのグラフを用意し、末尾から決定していく実装にしてしまっていました。

末尾からトポロジカルソートし、辞書順に大きい方から優先的に選ぶというものです。

しかし、これでは順序の前の方に大きい数がある可能性があるため、不適です。

例

3→1

という順序があった場合、2 1 3になってしまう。しかし、正しくは2 3 1です。