Codeforces Round 764 (Div. 3) C – Division by Two and Permutation を解いた記録
問題の概要
要素数\(n\)の数列\(A = \{a_{1}, a_{2}, \dots, a_{n}\}\)が与えられる．
次の操作を任意の回数（0回でもよい）行うことで，順列（\(1\)から\(n\)までの数がちょうど1つずつ存在する数列）を作れるか？
- \(1 \leq i \leq n\)を満たす\(i\)を選び，\(a_{i}\)を\(\lfloor a_{i} \rfloor\)に置き換える．
制約
- \(1 \leq n \leq 50\)
- \(1 \leq a_{i} \leq 10^{9}\)
- 入力はすべて整数
解法
最大二部マッチング問題を最大流問題に帰着できることを知っていれば，最大二部マッチング問題に落とし込んでライブラリパンチすればACできます．
下図のように数列の要素とその要素から作れる（順列の）要素の間に辺を張り，最大流を求めればよいです．
実装例
最大流を使わない解法
数列の要素のうち値の大きいものから順に，順列のどの要素とペアにするか考えることにします．
直感的に（？）順列の要素のうち値の大きいものはペアとなりうる相手が見つかりにくいとわかるので，ペアを作るときには順列の要素のうち値の大きいものを優先します．
というわけで，数列の要素を降順にソートしたあと数列の各要素について下記の操作を行えばACできます．
- 順列の要素のうちまだペアを組んでいないものとペアを組めるかチェック→ペアを組めるなら組む
- 組めないなら2で割る→1.に戻る