「グー」「チョキ」「パー」を出すことをそれぞれ文字 A, B, C で表し，参加者が出した手の列をこれらの文字からなる文字列として表します．また \(N=A+B+C\) とします．

---

[1] 独立な部分への分割

勝者の人数をスコアと呼ぶことにします．つまり，スコアとは

• BAB という連続 \(3\) 文字の並び
• CBC という連続 \(3\) 文字の並び
• ACA という連続 \(3\) 文字の並び

の個数の総和です．

ある \(2\) 人の参加者を，同時に連続する \(3\) 文字 BAB，CBC，ACA に含まれるときに同じグループに属するとして，参加者をグループに分割してみます．

言い換えれば，参加者の列を敗者と敗者の間で区切ることによって分割します．

すると本問題は，後述の例外を除き，次のように言い換えることができます．

\(A\) 個の A，\(B\) 個の B，\(C\) 個の C を持っている．以下の \(3\) タイプの操作によって，スコアを得ることができる．同じタイプの方法を複数回使うことも可能である．

• タイプ 1：\(n\) 個の A と \(n+1\) 個の B を消費して，スコア \(n\) を得る．
• タイプ 2：\(n\) 個の B と \(n+1\) 個の C を消費して，スコア \(n\) を得る．
• タイプ 3：\(n\) 個の C と \(n+1\) 個の A を消費して，スコア \(n\) を得る．

獲得可能なスコアの最大値を求めよ．

これらの操作は，各タイプの部分文字列を配置することに対応します．

例外となるのは，全体がひとつのグループになり，上の方法で部分文字列に区切られない場合です．つまり以下のような場合です．

• ABABAB...AB
• BCBCBC...BC
• CACACA...CA

これらの例外への対処は容易です．以下例外ケースを処理してある前提で，言い換えた後の問題を考えていきます．

---

[2] 解法

上で述べたように，\(3\) タイプの操作によってスコアを獲得していく問題だと見なします．

最適解においてさらに，次を仮定することができます．

• 同タイプの操作を行うのは \(1\) 回以下である．

なぜならば，同タイプの操作 \(2\) 回は，スコアを変えないまま \(1\) 回の操作にまとめられるからです．

• BABAB，BAB → BABABAB

結局各タイプに対する操作は \(0\) 回または \(1\) 回としてよいです．そこで以下のような場合分けによって解きます．

[2-1] \(3\) 種類の操作を行う場合

次のように考えることができます．

• はじめに A，B，C をひとつずつ消費する（消費できないならばこのようなケースは不可能である）．
• その後は，相異なる \(2\) 文字 AB，BC，CA のいずれかを消費するたびにスコアを \(1\) 獲得する．

\(x=A-1,y=B-1,z=C-1\) とします．対称性より \(x\leq y\leq z\) として考えればよいです．この場合最大スコアは次のようになります．

• \(x+y< z\) のとき：スコア最大値は \(x+y\)．
• \(z\leq x+y\) のとき：スコア最大値は \(\lfloor (x+y+z)/2\rfloor\)．

前者の証明

スコアを獲得するには `A` または `B` を消費する必要があるので，スコア最大値は $x+y$ 以下です．また，$x$ 個の `AC` と $y$ 個の `BC` を消費することでスコア $x+y$ を獲得することが可能です．

後者の証明

スコアを獲得するには $2$ 文字を消費するため $\lfloor (x+y+z)/2\rfloor$ 以下です．これが達成可能であることを示すには，余る文字の個数が $1$ 以下にできることを示せばよいです．常に個数の多い $2$ 文字を消費していくことで，これは達成可能です．

[2-2] \(2\) 種類の操作を行う場合

タイプ \(1, 2\) の操作を行うとします．このとき，次のように考えることができます．

• はじめに B，C をひとつずつ消費する（消費できないならばこのようなケースは不可能である）．
• その後は，AB，BC のいずれかを消費するたびにスコアを \(1\) 獲得する．

この場合には，A, B がひとつ以上余っている限りそれを AB として消費してもよい（そのような最適解が存在する）です．そのあと余った B, C の個数を見てスコアを計算すればよいです．

[2-3] \(1\) 種類以下の操作を行う場合

これまでと同様に考えればよいです．容易なので省略します．

---

[3] 実装について

各タイプの操作を行うか否かに注目すると，単純に見ると \(8\) 通りの場合分けがあります．下手に実装すると，似たような計算を \(8\) 回実装することになってしまい，実装量が増えたりミスが起こりやすくなります．適当な方法で実装をまとめるようにしましょう．例えば何らかの関数 f を実装した上で

f(A,B,C)
f(B,C,A)
f(C,A,B)

のように引数を入れ替えながら呼び出すというのがひとつの実装方法です．他に，

repeat 3 times:
  replace (A,B,C) by (B,C,A)
  // タイプ 1 のみの場合の計算を行う
  // タイプ 1, タイプ 2 のみの場合の計算を行う

のような実装方法もあります．

また本問では，すべてのパターンを場合分けして正確に処理しきることが必要で，おおよその解法は分かっていてもミスが起こりやすいと思います．このような問題では特に，ランダムテストによるデバッグ を行うことが有効になりやすいと思います．