SRM544 Div1 500

とぷこだ 過去問

問題

要素が0または1のH*Wの配列が与えられる。
配列の周りを罫線で囲んだものを考える時、左上の部分から右下の部分まで最短距離で結んだ線を引き、その線の下側になるすべての要素の0と1を反転することができる。

このとき、すべての要素を0にするために必要な最小の(上記の)操作回数を答える。

考え方

DPっぽく見えて、実はgreedyに解ける。実験してみる。


右側にでてくる1を必ずフリップしないといけないので、それをフリップする。
するとその行以降はその列までをすべてフリップしなければいけない。
それ以降の行では、その列より右側で1がでてきているところは同時にフリップしていける。

これを繰り返し、右上側から0を増やしていくようにすると、すべてフリップできる。


(変更できる最大の領域のフリップをし続けているので、感覚的に最適っぽいけど、証明むずい)


計算量は、愚直に実装しても、操作回数(最大50*50ぐらい？)*50*50なので、大丈夫。

反省

  • 確定領域を増やしていき、それが最小の動きならgreedyできそう。
    • どこから確定していけるかを考える
  • Petr先生が3分58秒とか脊髄反射で解いてるので、よくある問題なのかも。