2015JOI春合宿1-4 IOIOI Cards 解説

問題リンク

解説

$[L_i, R_i]$ を反転させる操作を、「$L_i$ から $R_i+1$ に移動する」もしくは「$R_i+1$ から $L_i$ に移動する」と言い換えると、次の3つのうち最小値を求める問題になる。

• $A$ から $A+B$ への距離 + $A+B+C$ から $A+B+C+D$ への距離
• $A$ から $A+B+C$ への距離 + $A+B$ から $A+B+C+D$ への距離
• $A$ から $A+B+C+D$ への距離 + $A+B$ から $A+B+C$ への距離

これはダイクストラ法で解けるので、この問題が $O(N\log max(N,A+B+C+D+E))$ で解けた。

提出リンク