きままにものづくり

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

SRM572Div1Easy

問題

サイズが50以下の文字列が与えられる。最初のK(1\leq K \leq 50)文字と最後のK文字が同じになるように変化させた時の、変更箇所の最小値を求めよ。

解法

ふたつのパターンに分けて考える。Nは文字列のサイズとする。
2*K \leq Nの場合、最初のK文字と最後のK文字のdiffをとる。
それ以外の場合、オーバーラップしている箇所により単純にdiffをとるだけではダメになる。依存関係はN-Kの間隔となる。このことに注意して、依存関係にある文字の数と、その文字の最大出現回数を引くことで部分解が得られる。これをすべての依存グループで計算することで答えが求まる。topcoder wikiの解説を見ると、このアルゴリズムを拡張することで、2*K \leq Nの場合にも対応させている。

計算量

O(N)
N:与えられる文字列のサイズ

コード

※今回のコードはmapを用いているのでinsertのコストがかかる。intの配列を用いることで上の計算量となる