2008JOI予選5 おせんべい 解説
解説
問題文中にもあるように、 が小さいことを利用します。
まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多くなるようにすればよいです。
計算量は となり、現実的な時間で計算できます。(というのも、このころのJOIは手元で実行して出力を提出する形式でした。)
小さめの制約が出てきたら、このような全探索を疑うことも重要です。
問題文中にもあるように、 が小さいことを利用します。
まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多くなるようにすればよいです。
計算量は となり、現実的な時間で計算できます。(というのも、このころのJOIは手元で実行して出力を提出する形式でした。)
小さめの制約が出てきたら、このような全探索を疑うことも重要です。