この問題はうまく全ての \(11/22\) 文字列を調べる方法を発見できるかが鍵となります。

答えを述べると、この問題は \(11/22\) 文字列の中央の / に注目することがポイントです。すなわち、中央の / を決め打った時の左右の 1, 2 の広がりを調べることにします。アルゴリズムを説明すると次のようになります。

• 答を管理する変数を ans とする。はじめ ans \(= 0\) である。
• \(i = 1, 2, \dots, N\) の順に次の操作を行う。
  • \(S[i] =\) / でない場合、何もしない。
  • \(S[i] =\) / である場合、左右に連続する 1, 2 の長さを管理する変数を \(d\) として(はじめ \(d = 0\) である)、次の一連の操作を繰り返す。
    • \(l = i - (d + 1), r = i + (d + 1)\) とする。
    • \(1 \leq l \leq N\) でない場合、繰り返しを終了する。
    • \(1 \leq r \leq N\) でない場合、繰り返しを終了する。
    • \(S[l] =\) 1 でない場合、繰り返しを終了する。
    • \(S[r] =\) 2 でない場合、繰り返しを終了する。
    • そうでない場合、両端についているのがそれぞれ 1, 2 ということになるので、\(11/22\) 文字列としての条件を満たしていることになる。よって \(d\) を \(d+1\) に更新する。
  • 得られた \(11/22\) 文字列の長さは \(1 + 2d\) であるから、ans を \(\max(\mathrm{ans}, 1 + 2d)\) に更新する。
• 最終的な ans の値が答えとなる。

計算量について考えます。この操作では \(1\) 回の繰り返しにつき最悪 \(\mathrm{O}(N)\) の計算量が掛かるので \(\mathrm{O}(N^2)\) になってしまうと考える方もいるかもしれませんが、実は計算量は \(\mathrm{O}(N)\) で済みます。 これは次のようにして証明できます。アルゴリズム内で「一連の操作」と呼ばれている部分の回数が \(\mathrm{O}(N)\) で抑えられれば計算量が \(\mathrm{O}(N)\) であると言えるので、これを証明します。\(1 \leq j \leq N\) を満たす各 \(j\) について、\(j\) が \(l\) として選ばれる回数を考えます。するとこれは、\(i\) が \(j\) から右を見て初めて現れる / である時に限られるので、\(j\) が \(l\) として選ばれるのは高々 \(1\) 回です。よって各 \(j\) について高々 \(1\) 回しか \(l\) として選ばれないため、「一連の操作」は高々 \(\mathrm{O}(N)\) 回であることが言えます。以上により証明できました。

よって上記のアルゴリズムは \(\mathrm{O}(N)\) で動作して、これは十分高速です。

• 実装例(C++)

#include <iostream>
#include <string>
using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;

  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] != '/') continue;
    int d = 0;
    while (true) {
      int j = i - (d + 1);
      int k = i + (d + 1);
      if (!(0 <= j and j < N)) break;
      if (!(0 <= k and k < N)) break;
      if (S[j] != '1') break;
      if (S[k] != '2') break;
      d++;
    }
    ans = max(ans, 1 + d * 2);
  }
  cout << ans << "\n";
}