AGC019-B：Reverse and Compare

問題

https://beta.atcoder.jp/contests/agc019/tasks/agc019_b

文字列 が与えられる。i <= i <= j <= n なる i, j を選んで部分文字列 a_i...a_j を反転させるという操作をするとき、操作によって何通りの文字列を得ることができるか。

考え方

求めるものは異なる文字列の数である。操作によって同じ文字列になる (i, j) について考える。

たとえば A=abcdb として (2, 5) を選択して反転すると A=abdcb となる。これは (3, 4) を選んで反転させた文字列と同じである。結論としては、(i, j) として選んだ文字の端点 a_i, a_j が a_i = a_j となる場合は別の a_i' ≠ a_j' (i < i', j' < j) なる a_i' ≠ a_j' によって同じ文字列を得ることができる。

よってすべての n(n-1)/2 通りの (i, j) の選び方から a_i = a_j となるような (i, j) を選ぶ場合の数を引けば良い。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            char[] s = in.nextString().toCharArray();
            long n = s.length;

            long[] a = new long[26];
            for (char c : s) {
                a[c-'a']++;
            }

            long ans = n * (n-1) / 2;
            for (long l : a) {
                ans -= l * (l-1) / 2;
            }
            out.println(ans + 1);
        }

ポイント

• 求める数はなにか
• 同じ結果になる場合はどのような場合か

類題