1269D - Domino for Young

• https://codeforces.com/contest/1269/problem/D
• editorialではよく証明が分からなかった
• こちらを見てわかった https://tinumukiti631.hatenablog.com/entry/2019/12/23/175055

同じ高さの２列があったら消してよい

• ぷよぷよじゃないしなぁ？と思うかもしれないが、

• このように右に寄せても消すことができるので、消してよい
• 2列じゃなくて4列などでも同様
• この消去を縦横に適用した後は、editorialでいうところのbasic型になるので、それはminで数えられる
• 消した分も考慮すると、全体としてmin(白の個数, 黒の個数)

発想

• 単純な形に変形する (今回でいうとbasic型)

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～