C. Smallest Word

1500
  • Quiz
  • AC
  • 解説
    • aaaaabbbbbの形にできる
    • aの塊ごとに見て、その後端で1度flipすると、そのaの塊が先頭に来る
    • 次のaの塊の直前にあるbで1度flipすると、先頭に集まっていたaの塊が後ろに来て、合体する（下図参照）
    • flipタイミングはコードの通り、"ab", "ba"を見ればいい。文字列の後端には番兵のように'b'を足した

f:id:peroon:20201202060050p:plain

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s;cin>>s;
    ll N = s.size();
    
    s.push_back('b');
    set<ll> se;
    rep(i,N){
      // tail a
      if(s[i]=='a' && s[i+1]=='b') se.insert(i);

      if(s[i]=='b' && s[i+1]=='a') se.insert(i);
    }

    VI Ans(N);
    rep(i,N){
      if(se.count(i))Ans[i]=1;
    }
    print_vector(Ans);

    return 0;
}