読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM 650 Div1 easy : TaroFillingAStringDiv1

Topcoder Div1 SRM

問題概要 :
長さNの文字列がある
初期状態ではそのうちのいくつかに'A'か'B'が書かれていて、
その他は何も書かれていない
これから何も書かれていない場所に'A'か'B'を書いていく
ただし何も書かれていない場所全てに'A'か'B'を書い後、隣接する2つの場所が同じ英小文字であるような場所の数が最小でなければならない ( このような場所のペアをuglinessという )
uglinessが最小となるような'A'と'B'の割り当て方は何通り存在するか?
答えを1000000007で割った余りを返せ

解法 :
'.'を何も書かれていない場所とする

A(奇数個 '.' が続く)A の場合, 最小のuglinessの数は0個
A ... A なら A BAB A のように両端と異なるものを割り当てればよいから
これより、両端が同じ英小文字でその間の空の場所の数が奇数ならその割り当て方は一意に定まる

A(偶数個 '.' が続く)A の場合, 最小のuglinessの数は1個
A .. A なら A BB A, A AB A, または A BA A のいずれか
A .... A について考える
A B..B A , この場合は同じ状態に戻るので再帰的に処理を続ける
A A..B A , この場合は既に1つuglinessができているのでその後の割り当て方は一意に定まる
A B..A A , この場合は1つ前の場合と同様で、割り当て方は一意に定まる

これらより、 A(偶数個 '.' が続く)A の場合は( 空白の数+1 )だけ割り当て方が存在することが分かる

A(奇数個 '.' が続く)Bの場合、最小のuglinessの数は1個
A ... B なら A BAA B, A BBA B, A ABA B, A BAB B のいずれか
A A...A B と A B...B B の場合は既に1つuglinessが1個あるのでその後の割り当て方は一意に定まる
その他の場合は再帰的に割り当てることになる

結局、この場合 2 + ( 連続する'.'の数 / 2 * 2 ) だけ割り当て方が存在することが分かる

連続する'.'の数が0か1の場合は割り当て方は一意に定まるので注意
また、これから割り当てる場所の両端のうち片方が '.' ならその割り当て方も一意に定まるので注意すること

コード :

typedef long long ll;
const int IINF = INT_MAX;
const ll MOD = 1000000007LL;

typedef pair<int,char> ic;

class TaroFillingAStringDiv1 {
public:
  
  ll compute(char prev_c,char next_c,int space){
    if( prev_c == '.' || next_c == '.' ) {
      return 1LL;
    } else {
      if( space == 0 ) return 1LL;
      if( prev_c == next_c ) {
        if( space == 1 ) return 1LL;
        if( space & 1 ) { // odd
          return 1LL;
        } else { // even
          return ( 1LL + (ll)space ) % MOD;
        }
      } else {
        if( space == 1 ) return 2LL;
        if( space & 1 ) { // odd
          ll multi = space / 2;
          return ( 2LL + multi * 2LL ) % MOD;
        } else { // even
          return 1LL;
        }
      }
    }
    return 1LL;
  }

  int getNumber( int N, vector <int> p, string s ) {
    deque<ic> deq;
    rep(i,p.size()) deq.push_back(ic(p[i]-1,s[i]));
    sort(deq.begin(),deq.end());
    if( deq[0].first != 0 ) deq.push_front(ic(0,'.'));
    if( deq.back().first != N-1 ) deq.push_back(ic(N-1,'.'));
    ll ret = 1;
    REP(i,1,deq.size()){
      char prev_c = deq[i-1].second;
      char next_c = deq[ i ].second;
      int free_space = deq[i].first - deq[i-1].first - 1;
      ( ret *= compute(prev_c,next_c,free_space) ) %= MOD;
    }
    return ret;
  }
};