この解説ではしばしば、問題文中の「試合」を文字列に対する操作と同一視します。また、文字列 \(X\) の \(l, l + 1, \ldots, r\) 文字目を連結した連続部分文字列を \(X[l,r]\) と表記します。ただし、\(l > r\) のとき \(X[l, r]\) は空文字列を表すものとします。

問題 1：文字列 \(S\) 中の R をすべて消すことは可能か？

もともと R がない場合、可能です。

R がある場合、P がなければ明らかに不可能です。

逆に、P があれば可能です。具体的には、R がある限り、次のように操作すればよいです。

• R と P が隣り合う部分があるならば、R を P で消す。
• R と P が隣り合う部分がないならば、R と S が隣り合う部分が必ずある。S を R で消す。

この操作で目的を達成できることは、操作によって P が消えることがないことなどから示せます。

まとめると、\(S\) に「R がないか、P がある」ことが条件です。

問題 2：文字列 \(S\) 中の S 以外をすべて消すことは可能か？

\(S\) が空文字列ならば可能です。そうでない場合を考えます。

最後に残る S のうち \(1\) 人を固定し、これを人 \(i\) とします。ある \(i\) が存在して、人 \(i\) を消さないまま R をすべて消すことができるならば可能で、そうでなければ不可能です。

\(S[1, i - 1]\) と \(S[i + 1, N]\) のそれぞれが、「R がないか、P がある」を満たしていれば、それは可能です。逆にそうでなければ、不可能です（問題 1 と比べて、人 \(i\) が端の P を消す操作が新たに可能になっていますが、これは役に立ちません）。

まとめると、\(S\) が以下のいずれかを満たすことが条件です。

• 空文字列である。
• 「R がないか、P がある」ような長さ \(0\) 以上の文字列 \(A, B\) を用いて、\(S = A \ + \) S \( + \ B\) と書ける。

問題 3：人 \(i\) が単独優勝する可能性はあるか？

\(S_i = \) R として一般性を失いません。

人 \(i\) を消さないまま残りの部分の S 以外をすべて消せるならば可能で、そうでなければ不可能です。

\(S[1, i - 1]\) と \(S[i + 1, N]\) のそれぞれが問題 2 の条件を満たしていれば、それは可能です。逆にそうでなければ、不可能です（人 \(i\) が端の S を消す操作が新たにできるようになっていますが、これも同様に役に立ちません）。

---

問題 3 を各 \(i\) について解けばよいです。（累積和などの適切な前計算のもと）S の位置を全探索すれば、各 \(i\) について \(O(N)\) となり、全体 \(O(N^2)\) となります。これを実装すると \(50\) 点が得られます。

満点解法のためには、問題 3 を解くパートを高速にできればよいです。そのための方針を 2 つ挙げます。

方針 1：動的計画法

動的計画法を利用します。たとえば、以下を状態として持ち、その状態が実現可能かどうかを値として持てばよいです。

• 何文字目まで見たか

• \(A \ + \) S \( + \ B\) のうちどの部分を作っているところか

• 今作っているところに R が出現したか

• 今作っているところに P が出現したか

この動的計画法は \(O(N)\) で動作します。これを左右から行うことで、各 \(i\) についての判定が \(O(1)\) で可能になります。全体計算量は \(O(N)\) です。

このような、特殊な定数個の状態を追加で持つ動的計画法は、みんなのプロコン 2019 D - Ears から、俗に「耳 DP」と呼ばれることもあります。

実装例

方針 2：問題 2 で調べる S を絞る

\(S[1, i - 1]\) について問題 2 を解くことについて考えます。これが解けたら、\(S[i + 1, N]\) についても同様にできます。

実は、最後に残る S のうちの \(1\) 人として選ぶ人 \(j\) の選び方は、次の \(2\) 通りのみを調べればよいです。

1. （\(S_j = \) S かつ、）\(S[1, j - 1]\) が「R がないか、P がある」を満たすような最小の \(j\)
2. \(i - 1\)

これを示します。1 の選び方で失敗するパターンは、\(S[j+ 1, i - 1]\) が「R があって P がない」場合です。これに加えてさらに、他の人 \(k\) を選んでいれば条件を満たしている、というパターンは、\(S[k + 1, i - 1]\) が「R も P もない」つまり「S のみからなる」場合しかありません。このとき、その S のうち最も右のものだけを見ればよいです。よって、この \(2\) 通りのみを調べればよいことが示せました。

累積和などの適切な前計算を \(O(N)\) で行うことで、各 \(i\) に対する判定を \(O(1)\) で行えるようにできます。全体計算量は \(O(N)\) です。

実装例