AtCoder Grand Contest 055 - ks2mのブログ

A - ABC Identity
- 思考過程

コンテスト前のレート：2038
レート通りのパフォーマンスが得られる順位：277位（1100点、231分44秒）

A - ABC Identity

問題
実装がだらだらと長くなった。

思考過程

部分列を $6$ 個作れるというところから、分解後の各部分列の長さはさておき、"ABC"の並び順については $3!$ 通りそれぞれを $1$ 個以下ずつ作りたい気がする。
例えば上記の $6$ 種類の内"BAC"のグループについては、 $S$ を長さ $N$ ずつ $3$ つに分け、最初の $N$ 文字から'B'のみ、次の $N$ 文字からは'A'のみ、最後の $N$ 文字からは'C'のみを割り当てるようにすると構成できる。
　
"BAC"グループの長さを $3K$ として、 $K$ の最大値は、 $min($ $S$ の最初 $N$ 文字内の'B'の個数、次の $N$ 文字内の'A'の個数、最後の $N$ 文字内の'C'の個数 $)$ となる。
"ABC", "ACB", "BAC", "BCA", "CAB", "CBA"の各グループについて上記3.の値を求め、それを元に上記2.の処理を行う。　→WA
　
適当な文字列をいくつか作って試してみると、各 $K$ の合計が $N$ を超えるパターンが出てきてしまったので、そうならないようにグループに割り当てた分は引いていく。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] s = br.readLine().toCharArray();
        br.close();

        int n2 = n * 2;
        int n3 = n * 3;
        // [0]：最初のN文字内、[1]：中央のN文字内、[2]：最後のN文字内の個数
        int[] a = new int[3];
        int[] b = new int[3];
        int[] c = new int[3];
        for (int i = 0; i < n3; i++) {
            if (s[i] == 'A') a[i / n]++;
            if (s[i] == 'B') b[i / n]++;
            if (s[i] == 'C') c[i / n]++;
        }

        int[] ans = new int[n3];
        int[] cnt = new int[6];
        cnt[0] = Math.min(Math.min(a[0], b[1]), c[2]);
        a[0] -= cnt[0];
        b[1] -= cnt[0];
        c[2] -= cnt[0];

        cnt[1] = Math.min(Math.min(a[0], c[1]), b[2]);
        a[0] -= cnt[1];
        c[1] -= cnt[1];
        b[2] -= cnt[1];

        cnt[2] = Math.min(Math.min(b[0], a[1]), c[2]);
        b[0] -= cnt[2];
        a[1] -= cnt[2];
        c[2] -= cnt[2];

        cnt[3] = Math.min(Math.min(b[0], c[1]), a[2]);
        b[0] -= cnt[3];
        c[1] -= cnt[3];
        a[2] -= cnt[3];

        cnt[4] = Math.min(Math.min(c[0], a[1]), b[2]);
        c[0] -= cnt[4];
        a[1] -= cnt[4];
        b[2] -= cnt[4];

        cnt[5] = Math.min(Math.min(c[0], b[1]), a[2]);
        c[0] -= cnt[5];
        b[1] -= cnt[5];
        a[2] -= cnt[5];

        int aa = 0;
        int bb = 0;
        int cc = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'A') {
                // 最初のN文字内に出てきた'A'の内、
                // cnt[0]個まではグループ0、以降はグループ1
                if (aa < cnt[0]) {
                    ans[i] = 0;
                    aa++;
                } else {
                    ans[i] = 1;
                }
            }
            if (s[i] == 'B') {
                if (bb < cnt[2]) {
                    ans[i] = 2;
                    bb++;
                } else {
                    ans[i] = 3;
                }
            }
            if (s[i] == 'C') {
                if (cc < cnt[4]) {
                    ans[i] = 4;
                    cc++;
                } else {
                    ans[i] = 5;
                }
            }
        }
        aa = 0;
        bb = 0;
        cc = 0;
        for (int i = n; i < n2; i++) {
            if (s[i] == 'A') {
                if (aa < cnt[2]) {
                    ans[i] = 2;
                    aa++;
                } else {
                    ans[i] = 4;
                }
            }
            if (s[i] == 'B') {
                if (bb < cnt[0]) {
                    ans[i] = 0;
                    bb++;
                } else {
                    ans[i] = 5;
                }
            }
            if (s[i] == 'C') {
                if (cc < cnt[1]) {
                    ans[i] = 1;
                    cc++;
                } else {
                    ans[i] = 3;
                }
            }
        }
        aa = 0;
        bb = 0;
        cc = 0;
        for (int i = n2; i < n3; i++) {
            if (s[i] == 'A') {
                if (aa < cnt[3]) {
                    ans[i] = 3;
                    aa++;
                } else {
                    ans[i] = 5;
                }
            }
            if (s[i] == 'B') {
                if (bb < cnt[1]) {
                    ans[i] = 1;
                    bb++;
                } else {
                    ans[i] = 4;
                }
            }
            if (s[i] == 'C') {
                if (cc < cnt[0]) {
                    ans[i] = 0;
                    cc++;
                } else {
                    ans[i] = 2;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n3; i++) {
            sb.append(ans[i] + 1);
        }
        System.out.println(sb.toString());
    }
}

ここまで38分46秒＋1ペナ。186位。

残り時間はほとんどB問題に使ったが、2時間以上かけて何もわからず。
一応最後の悪あがきとして、愚直に $O(N^2)$ で処理して1900msを超えたら"NO"ということをやってみたが当然通らず。

最終結果：Aの1完400点、43分46秒、372位、パフォーマンス1821
レート変動：2038→2018（-20）

1時間経過くらいの頃は1完でここまで下がるとは思っておらず、終わってみればちょうど2完最下位が損益分岐点だった。
Bで考えていたことは全くかすってもいなくて、CもDも問題チラ見して全くできる気はしなかったので仕方ない。