ARC117 C - Tricolor Pyramid の別解

# 概要
[AtCoder Regular Contest 117 C - Tricolor Pyramid](https://atcoder.jp/contests/arc117/tasks/arc117_c) を公式解説とは違う方法で解けたので、どのように解いたかをまとめてみました。説明が分かりにくい箇所があるかもしれませんがご了承ください。

問題文は以下の通りです。
>### 問題文
>$\,N\,$個の個のブロックが横一列に並んでおり、それぞれのブロックは青・白・赤のうちいずれかで塗られています。 左から$\,i\,$番目$\,(1\leq i\leq N)\,$のブロックの色は文字$\,c_i\,$で表され、$\,\mathtt{B}\,$は青、$\,\mathtt{W}\,$は白、$\,\mathtt{R}\,$は赤に対応しています。

>この状態から青・白・赤のブロックを積み上げ、$\,N\,$段のピラミッドの形にします。以下の図がその一例です。
![picture.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/374206d2-ce7c-498e-db0e-d292def4a4fa.png)
ここでは、ブロックを下から順に、以下の規則で$\,1\,$個ずつ置いていきます。

>+ 直下にある$\,2\,$個のブロックの色が同じ場合、それと同じ色のブロックを置く
>+ 直下にある$\,2\,$個のブロックの色が異なる場合、そのどちらでもない色のブロックを置く

>このとき、一番上のブロックはどの色になるでしょうか？

>### 制約
>+ $\,N\,$は$\,2\leq i\leq 400000\,$を満たす整数
>+ $c_1,c_2,...,c_N\,$はそれぞれ $\,\mathtt{B},\,\mathtt{W},\,\mathtt{R}\,$のいずれか

もちろん下の段から一段ずつブロックの色を求めていくと実行時間超過(TLE)に引っかかってしまうため、なにかしらの法則を見つけて計算を省略する必要があります。

# 解法

### 原理
公式解説では、$\,\mathtt{R}=0,\,\mathtt{W}=1,\mathtt{B}=2\,$と文字を整数に置き換えた上で、左右のブロックの整数を$\,p_1, p_2\,$と置いたときに、上のブロックの整数を$\,-(p_1+p_2)\bmod 3\,$と表せることから頂上のブロックの色を求めていますが、私はそんなことすら思いつかず、とりあえず何か規則性がないかと入力例を眺めていました。すると...
![joinus.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/6d616e07-2e1c-3c7e-eba9-ceeb11e91925.png)
上図のように、1辺4ブロックの正三角形の3頂点の色の関係が、ブロックの置き方のルールと一致しています！そこで、この仮説が常に成立すると決めつけ、これを使って高速に頂上のブロックの色を求められないか考えることにしました。

なお、コンテスト終了後に公式解説を見たところ、この仮説が正しいことが分かりました。
![integerise.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/3a82f0ad-ef99-8d98-0fdb-d940555c0eaa.png)

この法則に基づくと、1辺4ブロックの正三角形は、1辺2ブロックの正三角形に「圧縮」することができます。圧縮したものをさらに圧縮することもできます。

![show1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/dd5f144b-88fb-85c3-6dc5-2f606ae431ac.png)

ここで、圧縮後から逆にたどって圧縮前の正三角形を見ると、圧縮前の正三角形の3頂点のブロックの色と、1辺2ブロックに圧縮された正三角形の3つのブロックの色の配置が一致します。つまり、**圧縮可能な正三角形では、左下と右下の頂点のブロックの色さえ分かれば、その正三角形の頂上のブロックの色を求められる**、ということです。

これを使えば、圧縮可能な大きい正三角形を見つけることで、途中の段を省いてその頂上のブロックの色を一瞬で求めることができ、高速に答えを求められそうです。
<br>
### 頂上のブロックまでの求め方
圧縮可能な正三角形の1辺のブロック数を$\,l\,$とすると、圧縮前後の正三角形の1辺のブロック数の関係から、$\,l\,$は$\,l_1=2,\,l_n=3l_{n-1}-2\,$を満たす数列$\\{l_n\\}$の第$\,n\,$項$(n\geq 2)$で表せます。$\,l\,$の値が大きいほどより上段のブロックの色を求められるので、$\,l_n\leq N\,$を満たす$\,l_n\,$の最大値を求め、それを$\,l\,$に代入します。今回の制約では$\,2\leq N\leq 400000\,$ですから、漸化式を使った線形探索で十分高速に求められます。

はじめに色が分かっているのは一番下の段ですから、1辺$\,l\,$ブロックの正三角形の底辺を一番下の段に合わせ、正三角形を左から右へ1ブロックずつずらしていき、それぞれについて正三角形の左下と右下のブロックの色から頂上のブロックの色を求めることで、**下から$\,l\,$段目のブロックの色を求めることができます**。次に、ピラミッドの$\,l\,$段目から上を取り出すと、はじめと同様に一番下の段のブロックの色が分かっている小さなピラミッドができます。

そして、取り出した小さなピラミッドについて同様に、$\,l\,$の値を求め、下から$\,l\,$段目のブロックの色を求め、ピラミッドの$\,l\,$段目から上を取り出し、… と繰り返すと、最終的には1辺3ブロック以下のピラミッドができます。
後は一段ずつブロックの色を求めていけば、頂上のブロックの色を求めることができます。
![show2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/504da016-018d-de74-a64a-e2f61513feab.png)
<br>
### 実装
※変数名が雑ですが気にしないでください。
<br>
まずは、左下と右下のブロックの色から頂上のブロックの色を求める関数$\,\mathrm{func}()\,$を用意します。

次に、ピラミッドの1辺のブロック数が3以下になるまでの操作を作ります。
一番下の段のブロック数を$\,\mathrm{nn}\,$とすると、ピラミッドの1辺のブロック数は$\,\mathrm{nn}\,$ですから、前述した方法で$\,l\leq \mathrm{nn}\,$を満たす$\,l\,$の最大値を求めます。そして、ピラミッドの一番下の段のブロックの色を表す文字列を$\,\mathrm{befcc}\,$とし、下から$\,l\,$段目のブロックの色を求め、文字列$\,\mathrm{cc}\,$に格納します。
![show3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/729491/6cd7242e-e930-9995-24e8-30927abe4e43.png)

図のように、$\,\mathrm{cc}\,$の$\ i\,$文字目は$\mathrm{cc}[i]=\mathrm{func}(\mathrm{befcc}[i],\,\mathrm{befcc}[i+l-1])\,$で求めることができます。また、一番下の段のブロック数を$\,\mathrm{nn}\,$とすると、下から$\,l\,$段目のブロック数は$\,\mathrm{nn}-l+1\,$であるため、$0\leq i \lt \mathrm{nn}-l+1\,$を満たす$\,i\,$についてこの操作を行えば、$\mathrm{cc}$すなわち下から$\,l\,$段目のブロックの色を求められます。

その後、$\,\mathrm{befcc}\,$に$\,\mathrm{cc}\,$の値を代入し、$\,\mathrm{nn}\,$の値を$\,\mathrm{nn}-l+1\,$に更新すれば、「$\,l\,$段目から上のピラミッドを取り出す」操作を行えます。

以上の操作を、$\,\mathrm{nn}\gt 3\,$が満たされている間繰り返すことで、1辺3ブロック以下のピラミッドが取り出せます。
最後に、$\,\mathrm{nn}\gt 1\,$が満たされている間(つまり取り出したピラミッドが頂上のブロックのみになるまで)、$\,l=2\,$として上記の操作を繰り返すと、$\,\mathrm{befcc}\,$に頂上のブロックの色が格納され、答えを求めることが出来ました。
<br>
### コード例(C++)
[提出 #21869778 - https://atcoder.jp/contests/arc117/submissions/21869778](https://atcoder.jp/contests/arc117/submissions/21869778)

```c++
#include <bits/stdc++.h>
using namespace std;

#define stp(var, init, end) for (auto var = init; var < end; ++var)
#define ll long long

//左下と右下のブロックの色から頂上のブロックの色を求める関数
char func(char a, char b)
{
    if (a == b)
        return a;
    else
    {
        if ((a == 'B' && b == 'W') || (a == 'W' && b == 'B'))
            return 'R';
        else if ((a == 'R' && b == 'W') || (a == 'W' && b == 'R'))
            return 'B';
        else
            return 'W';
    }
}

int main(void)
{
    int n;
    string c;
    cin >> n >> c;

    int nn = n;
    string befcc = c; //一番下の段のブロックの色
    string cc = ""; //下からl段目のブロックの色
    while (nn > 3)
    {
        int l = 2;
        while (3 * l - 2 <= nn) //lの最大値を求める
        {
            l = 3 * l - 2;
        }
        stp(i, 0, nn - l + 1) //下からl段目のブロックの色を求める
        {
            cc += func(befcc[i], befcc[i + l - 1]);
        }
        //l段目から上のピラミッドを取り出す
        befcc = cc;
        cc = "";
        nn = nn - l + 1;
    }
    while (nn > 1)
    {
        stp(i, 0, nn - 1)
        {
            cc += func(befcc[i], befcc[i + 1]);
        }
        befcc = cc;
        cc = "";
        nn -= 1;
    }
    cout << befcc;
    return 0;
}
```

追記: 後から考えてみると、`while(nn > 3){ ... }`で$\,l\,$の最大値を求めるときの変数`l`の初期値が$\,2\,$なので、`while(nn > 1){ ... }`で行っている処理はそちらに統合できますね。完全に無駄コードでしたが、まあACできたので良しとしましょう。

<details><summary>修正後のコード</summary>
<div>
[提出 #22307181 - https://atcoder.jp/contests/arc117/submissions/22307181](https://atcoder.jp/contests/arc117/submissions/22307181)

```diff_cpp
// ...

int main(void)
{
    int n;
    string c;
    cin >> n >> c;

    int nn = n;
    string befcc = c;
    string cc = "";
-   while (nn > 3)
+   while (nn > 1)
    {
        int l = 2;
        while (3 * l - 2 <= nn)
        {
            l = 3 * l - 2;
        }
        stp(i, 0, nn - l + 1)
        {
            cc += func(befcc[i], befcc[i + l - 1]);
        }
        befcc = cc;
        cc = "";
        nn = nn - l + 1;
    }
-   while (nn > 1)
-   {
-       stp(i, 0, nn - 1)
-       {
-           cc += func(befcc[i], befcc[i + 1]);
-       }
-       befcc = cc;
-       cc = "";
-       nn -= 1;
-   }
    cout << befcc;
    return 0;
}
```
</div>
</details>

# 補足・感想
提出結果の実行時間を見ると23msなので、この方法で十分高速に求められることが分かりました。
追記: 計算量は$\,O(N)\,$とのことです。@square1001さんありがとうございます。

今回は偶然見つけた規則性から解答までたどり着けましたが、公式解説のように着実な計算により答えを求めることも大事ですし、解答へのアプローチ方法は多く知っているほどよいので、公式解説の方法を使ったコードも書いてみようと思います。