動く物が 3つある場合, 真ん中を全探索する のは典型.
\(E\) の場所を全探索して,\(M\) と \(X\) の場所を考える. \(M,X\) それぞれの値に対して,それが何個取り方があるのかを数える.
用意したいもの:
\(i \in N\) が与えられたとき, \([0,i)\) と \([i+1,N)\) それぞれにおいて, \(0,1,2\) がそれぞれ何個あるかを求める. 自分は \(0,1,2\) の position を記録して, binary search で数えた.
別解として累積和がある.数えたい対象の場所に \(1\)を, それ以外の場所に \(0\) を入れた配列で累積和をとれば 数えられる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll mex(ll a, ll b, ll c){
set<ll> st;
st.insert(a);
st.insert(b);
st.insert(c);
rep(i,4){
if(!in(i,st)) return i;
}
assert(false);
return -INFL;
}
int main() {
ll n ;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
string s; cin >> s;
vvll pm(3); // position m
vvll px(3);
rep(i,n){
if(s[i] == 'M') pm[a[i]].push_back(i);
if(s[i] == 'X') px[a[i]].push_back(i);
}
ll ans = 0;
rep(i,n) if(s[i] == 'E'){
// cout << "i : " << i << endl;
rep(l,3) rep(r,3){
auto itm = lower_bound(all(pm[l]), i);
auto itx = lower_bound(all(px[r]), i);
ll cm = itm - pm[l].begin();
ll cx = px[r].end() - itx;
ans += mex(l, a[i], r) * cm * cx;
}
}
cout << ans << endl;
return 0;
}