きままにものづくり

日々の気付いたことなんかを書いてます。

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に変えるためには、 \lceil \frac{c}{2} \rceil + 1回の操作が必要となる。SH、HSをすべてSHまたはHSに変えるために必要な操作回数が \lceil \frac{c}{2} \rceil となり、SHまたはHSをHHに変えるために1回の操作が必要になる。最後にSSの数を加えることで答えが求まる。

計算量

 O(N)

コード

広告を非表示にする