C - String Coloring AtCoder Grand Contest 026

C - String Coloring

問題概略

長さ2Nの文字列が与えられる。各文字を青と赤に塗り分けた時、左から青を読んだときと右から赤を読んだ時の文字列が同じ組み合わせはいくつあるか

制約

• $1\le N\le 18$
• $S$ の長さは $2N$ である
• $S$ は英小文字のみからなる

解法

2 ^ 36 は無理。こういう時は半分だけみたい。

片方の塗り方を決めると、もう片方の塗り方が何通りかに絞れる。

しかし、同じ塗り方を探索～とすると大変なので。そういう時は大抵mapに数えさせるとうまくいく。

また、左で赤く塗ったものが右で青く、左青が右赤で塗られていれば良い。

右をリバースして、青と赤を入れ替えると左右で同じ文字列を選ぶ問題になるので楽

そう考えていくと、左で2 ^18通りの塗り方をした時の文字列のペアを格納し、右でも同じことをして、左右で同じ組み合わせの個数をかけ合わせてやればよい。

問題の芯

ある条件を満たすものの個数を探索する時、丁寧に一つ一つ探索するよりも、全探索して、mapに数え上げさせると楽。

類題

D - 連結 / Connectivity

public static void main(String[] args)
    {
        N = sc.nextInt();
        char[] s = sc.next().toCharArray();
        char[] l = new char[N];
        char[] r = new char[N];
        System.arraycopy(s, 0, l, 0, N);
        System.arraycopy(s, N, r, 0, N);
        reverse(r);
        HashMap<P, Long> mapl = new HashMap<>();
        //左
        for (int m = 0; m < (1 << N); m++)
        {
            for (int i = 0; i < N; i++)
            {
                if (((m >> i) & 1) == 1) sb1.append(l[i]);
                else sb2.append(l[i]);
            }
            P key = new P(sb1.toString(), sb2.toString());
            Long kosu = mapl.get(key);
            mapl.put(key, kosu == null ? 1 : kosu + 1);
            sb1.setLength(0);
            sb2.setLength(0);
        }
        HashMap<P, Long> mapr = new HashMap<>();
        //右
        for (int m = 0; m < (1 << N); m++)
        {
            for (int i = 0; i < N; i++)
            {
                if (((m >> i) & 1) == 1) sb1.append(r[i]);
                else sb2.append(r[i]);
            }
            P key = new P(sb1.toString(), sb2.toString());
            Long kosu = mapr.get(key);
            mapr.put(key, kosu == null ? 1 : kosu + 1);
            sb1.setLength(0);
            sb2.setLength(0);
        }
        long cou = 0;
        for (Map.Entry<P, Long> enl : mapl.entrySet())
        {
            P key = enl.getKey();
            Long vl = mapl.get(key);
            Long vr = mapr.get(key);
            vl = vl == null ? 0 : vl;
            vr = vr == null ? 0 : vr;
            cou += vl * vr;
        }
        System.out.println(cou);

    }