ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC037 D - Sorting a Grid

問題
提出コード

解法

当たり前ですが、ある数字Xを取ってくると、最終的にどの行、どの列にいるべきか、というのが決まっています。
そこから逆算すると、3回目の操作開始時点では、

  • 全ての数について、いるべき行は正しい

という条件が成り立っていればよいです。なので、そこからさらに逆転して、2回目の操作開始時点では、

  • それぞれの列について、そこに存在する数字における最終的にいるべき行は全て異なる

という条件が必要なことがわかります。これが成り立っているとき、2回目の操作では、正しい行に移動してあげる、という操作をすればよいです(=それぞれの列ごとに数字をソートすればよいです)。
1回目の操作では、行の中で自由に順番を入れ替えることができます。
それぞれの数字について、最終的にいるべき行が決まっていて、1回目の操作後は、それぞれの列についてその値がバラバラになるようにする…
つまり、バラバラになるように"マッチング"をさせればよいです。
ということで、それぞれの列について順番に、合計M回マッチングを行います。
i回目のマッチングでは、i列目について、 "数字を置く行数"と、"最終的にいるべき行の値がなんであるか"をマッチングさせればよいです。
これを繰り返せば、フローを流し、復元を行うことで答えを求めることができます。

感想

フローと復元を行ったので実装が特別軽くはなく、AGCっぽくないと感じまてしまいました…