yukicoder No.2900 Star Divine

乱択を使うまいとして考えた解法が公式解説とやや異なっていたため、私の解法を記す。ここで、多重辺は先に除去しておく。

選ぶ赤い星の集合を決めた時、青い星は明らかに選べるだけ選ぶのが最適である。

ここで、選ぶ赤い星の集合を補集合に取り替えてみる。このとき、選べる青い星の集合はどのように変化するだろうか？

星をすべて選んだ時、奇数個の赤い星に隣り合っている青い星を明るい星と呼び、このような星を考える。明るい星は、選ぶ赤い星の集合を補集合にした時に選べるかどうかが入れ替わる。

逆に、偶数個の赤い星に隣り合っている青い星は暗い星と呼ぶ。暗い星は、選ぶ赤い星の集合を補集合にしても選べるかどうかは変わらない。

結局、選ぶ赤い星の集合を補集合に取り替えると、選べる明るい星の集合は補集合になり、選べる暗い星の集合は変わらない。選ぶ赤い星の数+選べる明るい星の数が大きい方にするのが明らかに良く、選べる暗い星が暗い星の半数以上を占めればよいことがわかる。

赤い星を順番に追加していく。その赤い星が最後に次数を操作することができる暗い星の集合を考えた時、この集合に含まれる星をより多く選べるようになればよいことがわかる。このように赤い星を選んで、条件を満たさなかったら赤い星を補集合に取り替えると必ず条件を満たす。

以上は

$O(x+y+m)$ で実装できる。