問題の観察

この問題はドミノしか存在せずフィールドの横幅が \(3\) しかないテトリスと捉えることができます. 主な相違点としては

• ドミノの回転はできない
• ドミノを横向きに置くときは, その下に間隔が空いてはならない
• スコアはすべてのミノを消したタイミングで \(1\) 加算される

が挙げられます.

そこで, 文字列 \(S\) に対応する操作列 \(X\) のスコアを決める手順はドミノの例を用いて説明することにし, 特に \(h_1=h_2=h_3\) となることを 平らになる と表現することにします.

\(S\) の特徴量

\(i=0,1,\dots ,N\) について, \(S\) の \(i\) 文字目までに登場する A の個数を \(a_i\) とし, B の個数を \(b_i\) とします.

ここで \(S\) の \(i\) 文字目までを処理したときに平らにできる条件について考えます. まずは簡単な考察から

• \(a_i+b_i\equiv 0\pmod 3\)
• \(b_i\equiv 0\pmod 2\)

が分かります. さらに, B が多すぎないこと, 具体的には

• \(b_i\le 2a_i\)

が必要です. このことは, 各段にある横向きのドミノの個数が高々 \(1\) 個であることから従います.

そこで, \(i=0,1,\dots ,N\) について \(V_i=2a_i-b_i\) と定めると, これまでの必要条件は

\[V_i\ge 0, V_i\equiv 0\pmod 6\]

と表せます. 同様にして, \(0\le i_1\lt i_2\lt \dots \lt i_k\le N\) に対して \(S\) の \(i_1,i_2,\dots i_k\) 文字目までを処理したときに, 各タイミングで平らにできる必要条件は

\[0\le V_{i_1}\le V_{i_2}\le \dots \le V_{i_k}\ , V_{i_1}\equiv V_{i_2}\equiv\cdots\equiv V_{i_k}\equiv 0\!\!\!\!\pmod 6\]

と表せます. 実は, この条件は十分条件でもあります. すなわち, 各タイミングで平らになるように操作列を構築することができます.

スコアの最大化

\((V_0,V_1,\dots ,V_N)\) の部分列 \((V_{i_0},V_{i_1},V_{l_2},\dots ,V_{i_k})\) であって,

• \(i_0=0\)
• \(V_{i_j}\equiv 0\pmod 6\ (j=0,1,\dots ,k)\)
• \(V_{i_j}\le V_{i_{j+1}}\ (j=0,1,\dots ,k-1)\)

を満たしているもののうち, 長さが最大のものを見つける問題になります. これはまさに最長非減少部分列問題であり, \(O(N\log N)\) 時間などで解くことができます.

答えとなる部分列 \((V_{i_0},V_{i_1},V_{l_2},\dots ,V_{i_k})\) を復元すれば, 問題は次のように分解されます.

\(j=0,1,\dots ,k-1\) について, 次のような問題に答えよ.

• \(S\) の \(V_{i_j}+1\) 文字目から \(V_{i_{j+1}}\) 文字目までを取り出した文字列を \(T_j\) とする.

• \(T_j\) に対応する操作列であって, 文字列をすべて処理したときに平らになるものを構築せよ.

操作列の構築

\(T_j\) を改めて \(S\) とおき, \(N\) も \(|S|\) にとり直します. \(V_i\) を先述のとおり定義します. ここで \(V_{N}\ge 0, V_N\equiv 0\pmod 6\) が成り立っています.

\(S\) に対応する操作列 \(X\) であって, 文字列をすべて処理したときに平らになるものを構築します.

基本となるアイデアは, A には 1 を, B には 3 を対応させれば, スコアが減ることはない, というものです. つまり

• \(S\) の \(i\) 文字目が A のとき \(X\) の \(i\) 文字目を 1 にする.
  • このことは, 縦向きのドミノは左端に置くことを意味する.
• \(S\) の \(i\) 文字目が B のとき \(X\) の \(i\) 文字目を 3 にする.
  • このことは, 横向きのドミノは右側に置くことを意味する.

このように操作をしている間, \(V_i\) は ドミノの左端の高さ \(h_1\) からドミノの中央の高さ \(h_2\) を引いた値になっています.

まず, \(V_N=0\) のとき, 基本のアイデアをそのまま実行すれば良いです. 以下, \(V_N\ge 6\) とします.

このときは, 縦向きのドミノの個数が実質 \(3\) 個以上余っていることになります. この余分な縦向きのドミノを適当なタイミングで同じ高さの場所に \(3\) つ並べてしまうことで \(V_N\) を \(6\) 減らした状態に帰着するということを行います.

\(V_i\ge 4\) となる最小の \(i\) に注目します. このとき \(S\) の \(i\) 文字目は A です.

\(V_{i-1}=2,V_i=4\) のとき

\(X\) の \(i\) 文字目を 1 の代わりに 2 にすることで, ドミノの左端の高さと中央の高さが揃い, 右端の高さが \(-2\) だけ高い状態になります. この状態を左右反転すれば, \(V_i=-2\) の状態に帰着します.

\(V_{i-1}=3,V_i=5\) のとき

\(i\) の最小性から \(V_{i-2}\neq 4\) であり, \(V_{i-2}=1\) です. つまり \(S\) の \(i-1\) 文字目も A です. この連続した A に対して, \(X\) の \(i-1\) 文字目を 1 の代わりに 2 に, \(X\) の \(i\) 文字目を 1 の代わりに 3 にすることで, \(V_i=-1\) の状態に帰着します.

以上を適切に処理することで, 所望の \(X\) を得ることができます.

まとめ

以下の処理を行えば良いです.

1. \(S\) に対応する \(V\) を求め, 最長非減少部分列問題を解く.
2. 分割された文字列に対して, 対応する操作列を基本アイデアを帰着の繰り返しによって構築する.

これらの処理はテストケース毎に \(O(|S|\log |S|)\) 時間の計算量で行うことができ, 十分高速に動作します.