SRM643Div1Medium

問題

2行N列の行列が与えられる。各要素はHかSである。以下の3つの操作を行い、すべての要素をHにするための最小の操作回数を求めよ。

• どれか一つの要素を選びXとし、それと隣り合っている要素を一つ選びYとする。Xの要素をYの要素に書き換える。
• 連続する列の要素を選び、隣合う列に書き換える。
• 任意の行を選び、隣り合う片方の行に書き換える。

解法

列のパターンはHH、HS、SH、SSの4パターンとなる。HHしかない場合は0を、SSしかない場合は-1を返す。HHとSSしかない場合は、SSの数が答えとなる。
HSとSHが変化する回数を数える。SH、SHをHHに変えるためには、回の操作が必要となる。SH、HSをすべてSHまたはHSに変えるために必要な操作回数がとなり、SHまたはHSをHHに変えるために1回の操作が必要になる。最後にSSの数を加えることで答えが求まる。

計算量

コード