問題を次のように読み替えます：

長さ \(N\) の列 \(SA\) が与えられます。各要素は M0,M1,M2,E0,E1,E2,X0,X1,X2 のいずれかです。
\(SA\) の長さ \(3\) の (連続とは限らない) 部分列 \(\binom{N}{3}\) 通りについて、それぞれ次のように得点を定めます。得点の合計はいくらですか？

• (M0,E0,X0) は \(\mathrm{MEX}(0,0,0)=1\) 点
• (M0,E0,X1) は \(\mathrm{MEX}(0,0,1)=2\) 点
• (M0,E0,X2) は \(\mathrm{MEX}(0,0,2)=1\) 点
• (M0,E1,X0) は \(\mathrm{MEX}(0,1,0)=2\) 点
• 以下略

このように読み替えた問題は明らかに「与えられた列 \(X\) の中に、指定された列 \(Y\) が (連続とは限らない) 部分列として何度登場しますか？」が解ければ答えることができ、これが \(O(|X||Y|)\) のDPで解けることは非常によく知られています。

例：ABC211C