AGC037 D - Sorting a Grid
解法
当たり前ですが、ある数字を取ってくると、最終的にどの行、どの列にいるべきか、というのが決まっています。
そこから逆算すると、3回目の操作開始時点では、
- 全ての数について、いるべき行は正しい
という条件が成り立っていればよいです。なので、そこからさらに逆転して、2回目の操作開始時点では、
- それぞれの列について、そこに存在する数字における最終的にいるべき行は全て異なる
という条件が必要なことがわかります。これが成り立っているとき、2回目の操作では、正しい行に移動してあげる、という操作をすればよいです(=それぞれの列ごとに数字をソートすればよいです)。
1回目の操作では、行の中で自由に順番を入れ替えることができます。
それぞれの数字について、最終的にいるべき行が決まっていて、1回目の操作後は、それぞれの列についてその値がバラバラになるようにする…
つまり、バラバラになるように"マッチング"をさせればよいです。
ということで、それぞれの列について順番に、合計回マッチングを行います。
回目のマッチングでは、
列目について、 "数字を置く行数"と、"最終的にいるべき行の値がなんであるか"をマッチングさせればよいです。
これを繰り返せば、フローを流し、復元を行うことで答えを求めることができます。
感想
フローと復元を行ったので実装が特別軽くはなく、AGCっぽくないと感じまてしまいました…
