ARC094 F - Normalization -

問題

F - Normalization

解法

この問題の部分問題として、S->Tに変換できるか考える。
まず、Sから変換している以上、同じ文字が連続している箇所がないとおかしい。
さらに、a->0 b->1 c->2 とそれぞれの文字に数字を割り当てS,Tを数列とみなしたとき、
(∑S) mod 3 == (∑T) mod 3
を満たしていないといけない。（これ気づくの不可能では）
例として
abc と ccc を比べてみると
abc -> 0 + 1 + 2 = 3
ccc -> 2 + 2 + 2 = 6
となり、mod 3 した値は等しくなる。
S.size == 4 のときをすべて示して、
S.size >= 5 のときはそれを元に帰納法っぽく証明できるらしい。

上のことが分かればあとはDPするだけ。 dp[index][今までの総和mod 3][前につかったやつ][同じ文字が連続したか]

場合分けとして、
S に含まれる文字が１種類のときは１を出力する。
S.size <= 3 の時は全探索
S.size >= 4 の時はDP（Sに同じ文字が連続した箇所がなければ+1(DPで数えてないので)）

ソースコード

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

const int MOD = 998244353;

string s;
vector<int> v;
int l;
int mod3_s;
map<vector<int>, bool> used;

int solve1(vector<int> now) {
  if ( used[now] ) return 0;
  used[now] = true;
  
  int ret = 1;
  for ( int i = 0; i < l-1; i++ ) {
    if ( now[i] != now[i+1] ) {
      vector<int> nxt = now;
      nxt[i] = nxt[i+1] = 3-now[i]-now[i+1];
      ret += solve1(nxt);
    }
  }
  
  return ret;
}

int dp[200001][3][4][2]; //dp[idx][mod 3][bool]
int solve2(int now, int mod3, int pre, int flag) {
  if ( now == l ) {
    if ( flag && mod3 == mod3_s ) return 1;
    else return 0;
  }
  if ( dp[now][mod3][pre][flag] >= 0 ) return dp[now][mod3][pre][flag];
  
  int ret = 0;
  for ( int i = 0; i < 3; i++) {
    ret += solve2(now+1, (mod3+i)%3, i, flag|(pre==i));
    ret %= MOD;
  }

  return dp[now][mod3][pre][flag] = ret%MOD;
}

int main() {
  cin >> s;
  l = s.size();
  for ( int i = 0; i < l; i++ ) v.push_back(s[i]-'a'), mod3_s += v[i];
  mod3_s %= 3;  

  if ( (((int)s.find("a") >= 0) + ((int)s.find("b") >= 0) + ((int)s.find("c") >= 0)) == 1 ) {
    cout << 1 << endl;
  } else if ( l <= 3 ) {
    cout << solve1(v) << endl;
  } else {
    fill_n(***dp, 200001*3*4*2, -1);
    int ans = solve2(0, 0, 3, 0);
    if ( !((int)s.find("aa") >= 0 || (int)s.find("bb") >= 0 || (int)s.find("cc") >= 0) ) ans++;
    cout << ans << endl;
  }
  
  return 0;
}

感想

文字列を数列にしてmod 3するみたいなのは考えもしなかった。
今後の解法の選択肢の一つとして覚えておきたい。