2008JOI予選5 おせんべい 解説

問題リンク

解説

問題文中にもあるように、 が小さいことを利用します。

まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多くなるようにすればよいです。

計算量は となり、現実的な時間で計算できます。（というのも、このころのJOIは手元で実行して出力を提出する形式でした。）

小さめの制約が出てきたら、このような全探索を疑うことも重要です。