C - Doukasen

公式解説の「衝突時間」ですが、以下のように考えられます。

$\frac{A_{i}}{B_{i}} $は導火線の一つの区間が燃えつきるのにかかる時間[秒]です。

これの和( $\sum_{i=0}^{N} { \frac{A_{i}}{B_{i}}}$ )は導火線全体が燃え尽きる時間となります。

今回は両側から焼いているため、この半分の時間で燃え尽きることになります。これが$T$になります。
(導火線の区間で燃える速度が違うのがだいぶややこしいですが、理屈の上では両側から焼いたら、全体が燃えるのにかかる時間は半分のはず)

なので、全体がきっかり半分の時間(=$T$)で燃え尽きる=片側から燃やして$T$秒経過したらもう片方の火にぶつかるはずです。

後は片側から燃やしていき、時間$T$でどれだけ燃えるかをfor文で計算します。

D - Restricted Permutation

トポロジカルソートを知っていると思いつけます。(知っていてもしばらく過ぎて思いつきませんでしたが)

トポロジカルソートが何かは

に譲ります。

今回の場合は、$A_{i}$から$B_{i}$を有向な辺でつなぐ制約を入れ、それをトポロジカルソートします。これだけではだめで、その結果が辞書順で最小になる必要があります。

トポロジカルソートする方法はDFSとBFSがありますが、今回はBFSがやりやすいようです(DFSで行ける方法をご存じの方はコメントお願いします。思いつかなかった)。

BFS版のアルゴリズムは以下がわかりやすかったです。

Topological sort from HCPC: 北海道大学競技プログラミングサークル

肝なのは、BFS版の場合、処理の途中で「入次数0の頂点」が複数ありえた場合、Queueからどう抜き取るかで、できるトポロジカルソート結果も変わることです。

入次数0の頂点の選び方がそのままトポロジカルソートの結果になるので、今回は、「辞書順で小さい」=番号が小さい方から選び出す必要があります。これはPriorityQueueを使うとラクです。

というわけで残りの解説は提出コードをご覧ください。 (DFS版も乗ってはいますが、使ってません)

C問題をややこしく考えすぎた。理屈の上では確かにこれで$T$が求まるが、直感的かと言われると、上で書いたぐらいに丁寧に書いてようやくなんとなく腑に落ちる感がある。