問題 解法 n文字からなる文字列の変換の典型として, 'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する この場合でも総和のmod3は保存されることがわかる. この非自明な必要条件が本質. 更に実験すればわかるが,1回以上の操作によって a[i] == a…

問題 解法 典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる. (は正規表現における閉包) i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう. それまでの最小の編集距離…

問題 問題概要 文字列Sが与えられる. 1回だけ,Sの i〜j文字目(1<=i

問題 問題概要 文字列Sが与えられる。 Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。 1 <= |S| <= 2*105 解法 回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」…