CODE FESTIVAL 2018 Final (Parallel)：D - Three Letters

問題

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d

考え方

考えていたこと

文字 A_i の長さについて 3 つの箇所を全探索というナイーブな考察以外に思いつかなかった...。3 文字なので、真ん中を固定して全探索して考えるとうまくいくことも多いが、解法は思いつかなかった。

あとは、最頻出の文字列について文字数が DP で求められたとすると文字列を復元できないか？最頻出の文字数が x 文字だとすると x は単調性があって二分探索でうまいことできないか？...などという明後日の方向の考察しか出てこなかった...。

解説見た

文字列の略称の候補を全探索する。その際に各文字について真ん中の文字 1 つを全探索して、左右の文字の候補については文字種類数で全探索する。略称の候補を数えるためには部分文字列のみが必要であって、文字の位置は問わないため。

そうすると計算量は \displaystyle O(\sum_{i=0}^{n-1} |S_i| * 52^2) = O(90000 * 52^2) \approx O(2.4 * 10^8) となり、C++で実装すると間に合う。Java だと TLE するのでかなり定数倍が重い。

実装テク

  • 左右の文字列の計算

ある文字についてその文字位置の左右に登場する文字数を計算するのは、予め文字位置の右に登場する文字を前計算し、文字を進めるごとにその文字を -1 し、左に登場することにするとよい。以下のような実装になる。

    int m = str.length;
    int[] L = new int[52], R = new int[52];
    fill(used, false);

    for (char c : str) R[c2i(c)]++;

    for (int i = 0; i < m; i++) {
        int n = c2i(str[i]);
        R[n]--;
        for (int left = 0; left < 52; left++) {
            for (int right = 0; right < 52; right++) {
                if (L[left] >= 1 && R[right] >= 1 && !used[left][n][right]) {
                    max = Math.max(max, ++cnt[left][n][right]);
                    used[left][n][right] = true;
                }
            }
        }
        L[n]++;
    }

Submission #4332300 - CODE FESTIVAL 2018 Final (Parallel)

どこに着目して考察するべきだったか

3 文字の真ん中を全探索。文字種類が 52 であるから、\displaystyle O(\sum_{i=0}^{n-1} |S_i| * 52^2) はギリギリ間に合うかも...という気持ちになると解ける。

何がバグっていたか

得た知見(典型ポイント)

  • 3点の真ん中を全探索

類題