We represent playing “Rock,” “Scissors,” and “Paper” by the characters A, B, C, respectively, and represent the sequence of hands played by participants as a string of these characters. We also let \(N=A+B+C\).

---

[1] Decomposition into independent parts

Let us call the number of winners the score. That is, the score is the total count of occurrences of:

• the consecutive \(3\)-character pattern BAB,
• the consecutive \(3\)-character pattern CBC,
• the consecutive \(3\)-character pattern ACA.

We say two participants belong to the same group if they are simultaneously included in the same consecutive \(3\)-character pattern BAB, CBC, or ACA, and partition the participants into groups.

In other words, we split the sequence of participants by cutting between consecutive losers.

Then, this problem can be rephrased as follows, except for the exceptions described later:

We have \(A\) copies of A, \(B\) copies of B, and \(C\) copies of C. We can earn score through the following three types of operations. The same type may be used multiple times.

• Type 1: Consume \(n\) copies of A and \(n+1\) copies of B to earn score \(n\).
• Type 2: Consume \(n\) copies of B and \(n+1\) copies of C to earn score \(n\).
• Type 3: Consume \(n\) copies of C and \(n+1\) copies of A to earn score \(n\).

Find the maximum achievable score.

These operations correspond to placing substrings of each type.

The exceptions are the cases where the whole forms a single group and cannot be split into substrings by the above method. That is, cases such as:

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

Handling these exceptions is straightforward. In the following, we assume the exceptional cases have been handled, and consider the rephrased problem.

---

[2] Solution

As described above, we view this as a problem of earning score through three types of operations.

In an optimal solution, we can additionally assume the following:

• Each type of operation is performed at most once.

This is because two operations of the same type can be merged into one operation without changing the score.

• BABAB, BAB → BABABAB

So we may assume each type is performed zero or one times. We solve by considering the following cases.

[2-1] Case where all three types of operations are performed

We can think of it as follows:

• First, consume one each of A, B, C (if this is impossible, this case is infeasible).
• After that, earn score \(1\) each time any of the \(2\)-character combinations AB, BC, CA is consumed.

Let \(x=A-1,y=B-1,z=C-1\). By symmetry, we may assume \(x\leq y\leq z\). In this case, the maximum score is as follows:

• If \(x+y< z\): the maximum score is \(x+y\).
• If \(z\leq x+y\): the maximum score is \(\lfloor (x+y+z)/2\rfloor\).

Proof of the former

To earn score, we must consume `A` or `B`, so the maximum score is at most $x+y$. Also, consuming $x$ copies of `AC` and $y$ copies of `BC` achieves score $x+y$.

Proof of the latter

Since each score requires consuming two characters, the maximum score is at most $\lfloor (x+y+z)/2\rfloor$. To show this is achievable, it suffices to show that the number of remaining characters can be made at most $1$. This is achievable by always consuming the two characters with the most copies.

[2-2] Case where exactly two types of operations are performed

Suppose we perform operations of types \(1\) and \(2\). We can think of it as follows:

• First, consume one each of B and C (if this is impossible, this case is infeasible).
• After that, earn score \(1\) each time either AB or BC is consumed.

In this case, as long as at least one each of A and B remain, we may consume them as AB (there exists an optimal solution that does so). Then, we compute the score by looking at the remaining counts of B and C.

[2-3] Case where at most one type of operation is performed

We proceed similarly to the above. We omit the details as they are straightforward.

---

[3] About the implementation

Focusing on whether each type of operation is performed or not, naively there are eight cases. A careless implementation would result in performing nearly identical computations eight times, increasing the implementation effort and the likelihood of mistakes. Try to organize the implementation appropriately. For example, one approach is to implement some function f and call it with permuted arguments:

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

Another implementation approach is:

repeat 3 times:
  replace (A,B,C) by (B,C,A)
  // compute the case with only type 1
  // compute the case with only types 1 and 2

Also, in this problem, it is necessary to handle all patterns correctly through casework, and even with a roughly correct solution, mistakes are likely to occur. For such problems, debugging with random tests (Japanese) is particularly effective.