AGC028-C Min Cost Cycle

問題リンク

解法

ちょっと考えると、撹乱順列を作るみたいな問題に帰着できる

ただ、ただの撹乱順列ではダメで、途中でループを作ってはいけないので、撹乱順列をふたつくっつけたようなものはダメというのも、サンプルを見てるとわかる

基本的には最小値でよくて、もし最小値が上の条件を満たさなければ、2番目の最小値を考えてやる これもダメだったら、考えられる3番目の最小値のうち、小さい方から 番目 (0-indexed) の値を使うほうは必ず条件を満たすことが示せるので、もう片方が条件を満たしていれば最小値を、そうでなければ条件を満たす片方を出力すればよい

感想

微妙に WA を生やしてしまった、こういうのはちゃんと詰めて一発で合わせたい。