JOI2015本選4 舞踏会 解説

問題リンク

解説

答えを二分探索する． 答えを決め打ちすればその答えよりある貴族の踊りが上手いか下手かだけが問題になる．

トーナメントのような表を描いて，「この位置にくる貴族の踊りが答えより 上手い/下手な 条件」を考えてやる． その子部分木で最低何人の答えより上手い貴族を割り当てる必要があるかが条件となるので，このような条件を持って順にシミュレーションしてやると，残りの配置できる貴族の踊りの上手さを参照して，その答えが実現可能かどうかが決定できる．

時間計算量は $O(N\log\max(D))$ となる．