読者です 読者をやめる 読者になる 読者になる

Codeforces Round #389 (Div. 2) D. Santa Claus and a Palindrome

問題

codeforces.com

考察

スコアが付いている幾つかの文字列を組み合わせ、回文となる文字列の中で最大のスコアを算出する問題です。

全ての文字列は同じ長さなので、これらで回文を作るのは以下の2パターンに分けられます。

  • ABA'型
  • AA'型

ここで、AとA'は鏡写しの関係です。
また、Bはそれ自身が回文です。
要は真ん中があるかどうかです。

これらをはじめとし、左右に1つずつ鏡写しのペアをくっつけていけば回文が出来上がります。

スコアを最大にする

各文字列は真ん中以外は必ず2つペアで用いるので、「2つの文字列のスコアを足して正なら答えに加え、それ以外なら無視する」という貪欲で最大のスコアが求まります。
また、小さなスコアの文字列を温存する必要もないため、大きい順に使うことができます。

たとえば、aabのスコア群が[5, 3, -5]、bbaのスコア群が[1, -2, -3, -3]であれば、[5, 1], [3, -2]の2つを答えに組み込むことができます。

真ん中

ただし、真ん中がある場合は、真ん中に置く場合と置かない場合で分岐をする必要があります。
たとえば、aaaのスコア群が[5, 3, 1, -4, -5]という場合、以下の2つの可能性があります。

真ん中あり: 5 + [3, 1]
真ん中なし: [5, 3]

スコアの計算

「今までに真ん中に置いたことがあるか?」ということをメモしておくDPで計算できます。
今回の場合は単純な貪欲なので、「真ん中に置いていない状態での最大スコア」「真ん中に置いたことのある状態での最大スコア」をそれぞれ記録し、「真ん中なし->真ん中なし」「真ん中なし->真ん中あり」「真ん中あり->真ん中あり」の3パターンで最大を順次記録してゆけば良いです。

実装上の注意点

「aaa」と「abb・bba」は区別する必要があるため、それぞれの文字列で回文かどうかを判定し、適したスコアの算出方法を使う必要があります。
また、普通にループをすると「abbでも処理をし、bbaでも処理をした」ということになるので、「abbを処理した後はbbaをスキップする」というような対処が必要です。

コード

int main() {
    int k, n;
    cin >> k >> n;
    unordered_map<string, vi> nums;
    rep(i, k) {
        string s1;
        int a;
        cin >> s1 >> a;
        nums[s1].push_back(a);
    }

    unordered_map<string, bool> used;
    int ans_no_center = 0;
    int ans_center = 0;

    tr(it, nums) {
        string s = it->first;
        vi que = it->second;
        sort(all(que), greater<int>());

        if(used[s])
            continue;

        // check - palindrome
        bool palin = true;
        rep(i, n / 2) {
            if(s[i] != s[n-1-i]) {
                palin = false;
                break;
            }
        }

        // whether centerize
        int nc = 0, c = 0;
        if(palin) {
            rep(i, que.size()-1) {
                if(que[i] + que[i+1] > 0)
                    nc += que[i] + que[i+1];
                i++;
            }

            c = que[0];
            REP(i, 1, que.size()-1) {
                if(que[i] + que[i+1] > 0)
                    c += que[i] + que[i+1];
                i++;
            }
        }
        else {
            string pal = s;
            reverse(all(pal));
            if(!nums[pal].empty()) {
                used[pal] = true;

                vi que2 = nums[pal];
                sort(all(que2), greater<int>());

                int que_size = min(que.size(), que2.size());
                rep(i, que_size) {
                    if(que[i] + que2[i] > 0)
                        nc += que[i] + que2[i];
                }
            }
        }

        chmax(ans_center,
              max(ans_no_center + c, ans_center + nc)
        );
        ans_no_center += nc;
        used[s] = true;
    }

    cout << max(ans_center, ans_no_center) << endl;
    
    return 0;
}

感想

vectorなのに名前がqueになっているのはご愛嬌(priority_queueを使おうかと思っていましたが、vectorを逐次ソートした方が楽だったため)