きままにものづくり

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

SRM592Div1Easy

問題

サイズNの文字列が与えられる。各要素はR,G,Bのどれかである。何もない文字列から始め、一文字ずつ文字を加え与えられた文字列にする時の最高のスコアを求めよ。
スコアは以下のように追加される。

  • 初めの要素の場合は0ポイント
  • 文字列の端に追加した場合は、もとの文字列の文字の種類の分だけスコアを足す
  • 文字列の間に追加した場合は、左右の文字列の文字の種類の分だけスコアを足す

解法

左用と右用の集合を用意し、それに追加してくことで答えが求まる。

計算量

 O(N log N)

コード

広告を非表示にする