OMCE011(B)

　$\{a_i\}$ に対して数列 $\{b_i\}$ を次のように定義する:

• $n$ 以下の正整数 $i$ であって，$(a_i,a_{i+1},a_{i+2})=(1,2,3)$ なるもの全てに対して，$a_{i+1}$ を削除した数列．

このとき，$\{b_i\}$ の要素数は $n-123$ であり，$b_{n-122}=b_1, ~ b_{n-121}=b_2$ と定義すると，全ての $n-123$ 以下の正整数 $k$ で $b_{k-1} \neq b_k$ が成り立ち，かつ $n-123$ 以下の正整数 $i$ のうち，

• $(b_i,b_{i+1})=(1,3)$ となるものがちょうど $255$ 個
• $(b_i,b_{i+1})=(2,1)$ となるものがちょうど $213$ 個
• $(b_i,b_{i+1})=(3,2)$ となるものがちょうど $321$ 個
• $(b_i,b_{i+1},b_{i+2})=(1,2,3)$ となるものがちょうど $0$ 個

ずつ存在する．逆に，正の整数 $n$ に対してこのような $\{b_i\}$ が存在すれば，条件を満たす $\{a_i\}$ も存在する．
　さて，頂点を $1,2,3$ とし，$n-123$ 本の辺 $e_1, e_2, \ldots, e_{n-123}$ をもつ有向グラフであって，辺 $e_i$ が $b_i$ と $b_{i+1}$ をこの順に結んでいるようなものを考える．このとき $b_{k-1} \neq b_k$ より自己ループは存在せず，さらに

• $1$ から $3$ へのびる辺は $255$ 本
• $2$ から $1$ へのびる辺は $213$ 本
• $3$ から $2$ へのびる辺は $321$ 本

ずつ存在する．$1$ から $2$ へ向かう辺の本数を $m \ge 0$ とすると，頂点 $k$ を始点・終点とする辺の数は $k$ によらず等しいので，

• $2$ から $3$ へのびる辺は $m+108$ 本
• $3$ から $1$ へのびる辺は $m+42$ 本

だけ存在する．ここで $m \gt 213$ のとき，鳩ノ巣原理より $e_i$ が $1$ から $2$ へ向かい，$e_{i+1}$ が $2$ から $3$ へ向かうような $i$ が存在し，題意に則さない．したがって $m \le 213$ である．逆に，$m\leq 213$ である限り，対応する $\{b_i\}$ であって $(b_i,b_{i+1},b_{i+2})=(1,2,3)$ となる $i$ が存在しないようなものを構成することができるから，$m=0,\ldots,213$ の場合，またその場合に限り，$\{b_i\}$ を構成できる．

　さて，$\{b_i\}$ の要素数はグラフの辺の総本数 $3m+939$ に等しいため，$n=3m+1062$ であり，求める値は $$\sum_{m=0}^{213} (3m+1062)=\mathbf{295641}$$ である．