きままにものづくりスマートフォン用の表示で見るきままにものづくり日々の気付いたことなんかを書いてます。この広告は、90日以上更新していないブログに表示しています。2013-10-03SRM572Div1Easy問題サイズが50以下の文字列が与えられる。)文字と最後のK文字が同じになるように変化させた時の、変更箇所の最小値を求めよ。解法ふたつのパターンに分けて考える。Nは文字列のサイズとする。場合、最初のK文字と最後のK文字のdiffをとる。それ以外の場合、オーバーラップしている箇所により単純にdiffをとるだけではダメになる。依存関係はN-Kの間隔となる。このことに注意して、依存関係にある文字の数と、その文字の最大出現回数を引くことで部分解が得られる。これをすべての依存グループで計算することで答えが求まる。場合にも対応させている。計算量O(N)N:与えられる文字列のサイズコード※今回のコードはmapを用いているのでinsertのコストがかかる。(1)月別アーカイブはてなブログをはじめよう!even_ekoさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。