問題
https://codeforces.com/contest/1327/problem/B
問題概要
ある国にn人の王女がおり、隣国にn人の王子がいる。
国王はできるだけ多くの王女と王子を結婚させたい。王女たちはそれぞれ意中の相手が0からn人おり、国王は長女から順に、彼女の意中の相手のうち年齢の高い方を優先して嫁がせることにした。また意中の相手が既に年長の王女に取られている場合はその王女は改めて他の相手を選ぶことはできない。
国王はできるだけ多くの王女を嫁がせたいが、時間がないので一人の王女に一人だけ意中の相手を増やすように説得することにした。
その説得により増やせる可能性のあるカップルを一組答えよ。また、説得でカップルを増やすことができない場合はその旨を答えよ。
(以上は、元問題で王女王子に振られている番号が長男長女から順に昇順であると解釈した文章になります)
考察
やたら問題文が長いのですが、とりあえず問題文で指示されたとおりの操作をやってみて、王女王子が余らなければ"OPTIMAL"です。
余った場合、余った王女と王子をどの組でもいいので組み合わせればいいです。余った王子はどの王女にも指名されていないか、されていても優先順位が低く別の王子とカップルになっているため、余った王女が取ってしまっても既存のカップルに影響を与えず一組増やすことができます。