　一般に正 $N$ 角形（$N$ は $3$ 以上の整数）に対して考える． 正 $N$ 角形の頂点を順に $A_1,A_2, \ldots ,A_N$ とし，頂点の添字は $N$ を法として考える．また，頂点 $A_i$ に塗られた色を $C_i$ とする． \
　以下，スコアの $2$ 乗の総和を求める．ここで，
$$\begin{aligned}
(スコアの二乗) &= (C_i=C_{i+1}となる\\, i\\, の個数)^2 \\\\
&= (C_i=C_{i+1}となる\\, i\\, の個数) \times (C_j=C_{j+1}となる\\, j\\, の個数)
\end{aligned}$$
により，二つの辺からなる組それぞれの寄与を考えれば良い．

----

i) $i=j$ のとき \
　 $i=j$ の選び方は $N$ 通り， $C_i=C_{i+1}$ の選び方は $3$ 通り，他の色の選び方は $3^{N-2}$ 通りより，

$$N \times 3 \times 3^{N-2}=3N \times 3^{N-2}$$

ii) $|i-j|=1$ のとき \
　 $i,j$ の選び方は $2N$ 通り， $C_{\min(i,j)}=C_{\min(i,j)+1}=C_{\min(i,j)+2}$ の選び方は $3$ 通り，他の色の選び方は $3^{N-3}$ 通りより，

$$2N \times 3 \times 3^{N-3}=2N \times 3^{N-2}$$

iii) $|i-j| \geq 2$ のとき \
　 $i,j$ の選び方は $N(N-3)$ 通り， $C_i=C_{i+1},C_j=C_{j+1}$ の選び方は $3^2$ 通り，他の色の選び方は $3^{N-4}$ 通りより，

$$N(N-3) \times 3^2 \times 3^{N-4}=N(N-3) \times 3^{N-2}$$

----

　i),ii),iii) より，スコアの $2$ 乗の合計は

$$3N \times 3^{N-2} + 2N \times 3^{N-2} + N(N-3) \times 3^{N-2} = N(N+2) \times 3^{N-2}.$$

よって，平均は $\dfrac{N(N+2)}{9}$ であり，特に $N=333$ のときこの値は $\mathbf{12395}$ である．
公式解説
https://onlinemathcontest.com/contests/omc213/editorial/8567
　一般に正 $N$ 角形に対して考える．$N$ 本の辺に対して，次のようにスコア $x_1, \cdots, x_n$ を定義する．

- 両端の頂点が同じ色であれば $x_i=1$，そうでなければ $x_i=0$

　色の塗り方 $3^N$ 通りが同様に確からしいと仮定すると，各 $x_i$ は確率変数であり，いま求めるべきは $\left( \sum\limits_{i=1}^{N} x_i \right)^2$ の期待値に一致する．以下，期待値は $E(*)$ で表す．\
明らかに $E(x_i)=E(x_i^2)=\dfrac{1}{3}$ であり，$E(x_i x_j)=E(x_i)E(x_j)=\dfrac{1}{9}$ であること（$x_i$ と $x_j$ の独立性）も容易に確認できる．従って
$$E(\left( \sum\limits_{i=1}^{N} x_i \right)^2) =\sum\limits_{i=1}^{N} E(x_i^2)+\sum\limits_{i \neq j} E(x_i x_j)=N×\dfrac{1}{3}+N(N-1)×\dfrac{1}{9}=\dfrac{N(N+2)}{9}$$
期待値の性質を用いる方法
https://onlinemathcontest.com/contests/omc213/editorial/8567/440
　一般に, $N$ 角形 $N\ge 1$ の場合を考えます.   
全ての塗り方のうち, 丁度 $k$ 箇所の辺について両端の色が等しくなるような塗り方の総数を $f(k)$ とすると, 求めるものは 
$$Ans=\frac{\sum\_{k=0}\^{N}k\^{2}f(k)}{3\^{N}}$$
です.  
まず $f(k)$ を求めましょう.  

$k\lt N$ の時を考えます.  
$N$ 個の頂点に時計回りに $1,2,\dots,N$ と番号をつけ, 頂点 $i-1,i$ の色が等しいような頂点 $i$ を「良い頂点」と呼ぶことにします. ただし, 頂点 $0$ とは 頂点 $N$ のことです.  
すると, 良い頂点を丁度 $k$ 個選ぶ方法は $\binom{N}{k}$ 通りあります.  
ここで, 良い頂点の選び方を一つ固定し, 良い頂点の集合がそうなるような着色方法を考えます.  

良い頂点が連続する区間は頂点が同じ色で塗られるため, 良い頂点の連続区間をひとつのかたまりととらえることで, これは以下の問題の $n=N-k$ の場合に帰着されます.   

---

正 $n$ 角形の各頂点に $3$ 種類の色を塗る方法であって, 辺で隣接する $2$ 頂点には異なる色が塗られる塗分け方はいくつあるか? 

---

この問題の答えを, $g(n)$ とします.  
結論から述べると, この問題は以下のような一般項で明示的に表されます.  

$$g(n)=\begin{cases}
1&(n=0)\\\\
2\^{n}+2\times (-1)\^{n}&(n\neq 0)
\end{cases}$$

<details> <summary> 導出の概略  <\/summary> 

頂点 $1,n-1$ の色が異なる時, 頂点 $n$ に書き込む色は $1$ 通り, 頂点 $1,n-1$ の色が等しい時, 頂点 $1, n-2$ の色が異なり, 頂点 $n-1,n$ の色の決め方は $2$ 通りある.  よって, 

$$g(n)=g(n-1)+2g(n-2)\ (n\ge 3)$$ 

という漸化式がたつ.  これを解き, $n$ が小さい場合も確認すれば上記の一般項を得る.
 <\/details>

(注: $n=1$ の場合に隣り合う頂点が無いから $g(1)=3$ では? と思った方もいるかもしれませんが, 今回の設定の場合頂点 $1$ と頂点 $1$ は辺で結ばれていると考えるため, 常に不適切すなわち $g(1)=0$ となります.  )  

従って, $f(k)=\binom{N}{k}g(N-k)=\binom{N}{k}(2\^{N-k}+2\times(-1)\^{N-k})$ となります.  
ここで, 除外をしていた $k=N$ の場合もこの式が成立することが確かめられます.  

以上を整理すると, 求める答えは

$$\begin{aligned}
3\^{N}\times Ans&=\sum\_{k=0}\^{N}k\^{2}f(k)\\\\
&=\sum\_{k=0}\^{N}k\^{2}\binom{N}{k}(2\^{N-k}+2(-1)\^{N-k})\\\\
&=N\times 3\^{N-2}\times(N+2)
\end{aligned}$$

より所望の答えを得ます.  

ただし, 最終行にかけては, 

$$\sum\_{k=0}\^{N}k\^2\binom{N}{k}a\^{N-k}=N(1+a)\^{N-2}(N+a)$$

を用いており, これの導出は例えば以下の問題の解説が参考になります. 
<details> <summary> 過去の問題例  <\/summary> 

- OMC161(E)
- OMC210(C)

 <\/details>
ユーザー解説
https://onlinemathcontest.com/contests/omc213/editorial/8567/442
　向きを固定した正 $333$ 角形の各頂点を，赤・青・緑の三色から一つずつ選んで塗り，それぞれの塗り方に対してその**スコア**を以下で定めます：

- 正 $333$ 角形の辺のうち，両端の頂点の色が等しいものの数

　回転によって一致する色の塗り方を区別した場合の $3^{333}$ 通りすべてについて，それぞれのスコアの $2$ 乗の（相加）平均を求めてください．