固定して考える ABC375 D - ABAを理解し忘れないようにする

https://atcoder.jp/contests/abc375/tasks/abc375_d

記事の概要

• ABC375Dでコンテスト中に考えた内容と、解説や提出コードを読んで理解したことを記載します。

使用アルゴリズム、データ構造、典型考察

• 固定して考える
  • 変数が２つ以上ある際に片方だけ通常通りループを回して、もう１つを工夫によって求めることで$O(N^{2以上})$を解消するテクニックを学ぶことができます。

問題概要

$1 <= i < j < k <= |S|$で$Si,Sj,Sk$を結合した際に回文になる個数を出力する。

コンテスト中に考えたこと

• 前提として文字列の内、左端と右端が同じ、つまり$Si == Sk$であれば回文となる。
• $O(|S|^3)$をどう改善するか
  • 改善点を思いつかず

解説見た

• 真ん中のjを固定して、そこからiとkを逆算して求める。
• iの文字の数とkの文字の数を管理しておき、掛け算することで回文の個数を求められる。
  • left_count = {'a': 1,'b': '2'},right_count = {'a': '2': 'b': 0}の場合
    • a文字は$1 \times 2$で2個、回文がある。b文字は$2 \times 0$で回文はないことが分かる。

提出コード

解説放送の提出コードコードを抜粋し、シミュレーションして理解度を深めます。
https://atcoder.jp/contests/abc375/submissions/58735627

int main() {
    string s;
    cin >> s;
    vector<int> lcnt(26);
    vector<int> rcnt(26);
    int n = s.size();
    // 不要な分岐を減らすためにまずjを含めたrcntを持っておく。
    rep(i,n) rcnt[s[i]-'A']++;
    ll ans = 0;
    rep(j,n) {
      // 真ん中s[j]は計算したくないのでまず引く。
      rcnt[s[j]-'A']--;
      // 回文個数計算
      rep(c,26) ans += (ll)rcnt[c] * lcnt[c];
      // jを動かすことによってiの文字の個数を更新する。
      lcnt[s[j]-'A']++;
    }
    cout << ans << endl;
    return 0;
}

補足

こういった２つ以上の変数がある場合、一方を固定しもう片方を工夫によって求められる問題は典型考察。
また３つ以上の変数がある場合は、真ん中を固定すると今回のようにうまくいくケースが多いみたい。
以下参照

https://algo-logic.info/how-to-think-cp/#:~:text=うまくいきます。-,固定して考える,-変数がいくつか

記事作成時間　60分