不定期プログラミング覚え書き

青コーダーと黄コーダーの間を彷徨う社会人プロコン勢が余力のあるときに復習した内容をまとめるブログ

SRM 553

TopCoder

平日午前はマジ勘弁、後日EasyとMediumだけ解きました。

Easy Suminator

問題

正の数字列を以下の規則に基づきプログラムとして解釈するものとする。

  • 0以外の数字が来た：プログラムスタックに数字をpush
  • 0が来た：スタックの上２つをpop（スタックが空ならばpop時には0を返す）して足した値をpush
  • 最終結果：スタックの一番上の値

一箇所だけ虫食いが存在（-1が入っている)しているプログラム(program)と、最終結果wantedResultが渡される。
この結果を返すように虫食いの箇所に数字を入れよ。もしも複数の数字が可能ならば最小のものを返せ。
なお、プログラムには 1000000000以下0以上の数字しか含まれていないものとする。

考えたこと

虫食いの値が0であるときとそうでない場合をそれぞれシミュレーションすれば良いのでは？
0でない値はXだとして、Xの係数を引き継ぐような計算をしとけばおｋ．

コード
  ll get( stack<ll> st){
    if( st.empty() ) return 0;
    else{
      ll ret = st.top();
      //st.pop();
      return ret;
    }
  }
  int findMissing(vector <int> program, int wantedResult) {
    int result;
    stack<ll> st0;
    stack<ll> st1;
    stack<ll> st2;
    for( int i = 0 ; i < (int)program.size(); i++ ){
      if(program[i]==0){
        ll a=get(st0);
        if( !st0.empty() ) st0.pop();
        ll b=get(st0);
        if( !st0.empty() ) st0.pop();
    //    cout << a<< " +" << b << endl;
        st0.push( a+ b );
        
        a = get(st1);
        if( !st1.empty() ) st1.pop();
        b = get(st1);
        if( !st1.empty() ) st1.pop();
        st1.push(a+b);

        a= get(st2);
        if( !st2.empty() ) st2.pop();
        b= get(st2);
        if( !st2.empty() ) st2.pop();
        st2.push(a+b);
      }
      else if(program[i]==-1){
        ll a=get(st0);
        if( !st0.empty() ) st0.pop();
        ll b=get(st0);
        if( !st0.empty() ) st0.pop();
      //  cout << a<< " +" << b << endl;
        st0.push(a+b);
        st1.push(0);
        st2.push(1);
      }
      else{
        st0.push(program[i]);
        st1.push(program[i]);
        st2.push(0);
      }

    cout << st0.top() << endl;
    cout << st1.top() << "+"  << st2.top() <<"*X" << endl;
    }
    cout << endl;
    cout << st0.top() << endl;
    cout << st1.top() << "+"  << st2.top() <<"*X" << endl;
    if( st0.top() == wantedResult ) return 0;
    
    if( st1.top() == wantedResult ){
      if( st2.top() == 0 ) return 1;
      else return -1;
    }
    else{
      if( st2.top() == 0 ) return -1;
      if( (wantedResult-st1.top()) % st2.top() != 0 ) return -1; 
      ll ret = (wantedResult-st1.top())/st2.top();
      if( ret > 0 && ret <= 1000000000 ) return ret;
      return -1;
    }
    return result;
  }

stackを函数に引数で渡してpopさせたら失敗した。どうやらコピー渡しだったようだ。
最近このあたりの扱い杜撰過ぎてひどいなあ。

参照渡しとかコピー渡しとかについて確認

なんで今まで調べてなかったのかと小一時間問い詰めたい。
cppだと引数のtypeの後に&をつければ参照渡しになるんだそうな。
参照渡しにして書いたらほんの少しだけコードがましになっただろうか。

  ll get( stack<ll> &st){
    if( st.empty() ) return 0;
    else{
      ll ret = st.top();
      st.pop();
      return ret;
    }
  }
  int findMissing(vector <int> program, int wantedResult) {
    int result;
    stack<ll> st0;
    stack<ll> st1;
    stack<ll> st2;
    for( int i = 0 ; i < (int)program.size(); i++ ){
      if(program[i]==0){
        ll a=get(st0);
        ll b=get(st0);
        st0.push( a+ b );
        
        a = get(st1);
        b = get(st1);
        st1.push(a+b);

        a= get(st2);
        b= get(st2);
        st2.push(a+b);
      }
      else if(program[i]==-1){
        ll a=get(st0);
        ll b=get(st0);
        st0.push(a+b);
        st1.push(0);
        st2.push(1);
      }
      else{
        st0.push(program[i]);
        st1.push(program[i]);
        st2.push(0);
      }

    }
    if( st0.top() == wantedResult ) return 0;
    
    if( st1.top() == wantedResult ){
      if( st2.top() == 0 ) return 1;
      else return -1;
    }
    else{
      if( st2.top() == 0 ) return -1;
      if( (wantedResult-st1.top()) % st2.top() != 0 ) return -1; 
      ll ret = (wantedResult-st1.top())/st2.top();
      if( ret > 0 && ret <= 1000000000 ) return ret;
      return -1;
    }
    return result;
  }

Medium TwoConvexShapes

問題

W(白),B(黒),?が並んで居る盤面が引数(grid)として与えられる。
?の中にWorBを埋めて、Wの領域とBの領域がそれぞれconvexとなるような２つの領域に分割されるパターン数を返せ。

考えたこと

Bが設置された始点をx,終点をyとして、[x,y]領域のパターン数を各列ごとに更新していけば良い？
とか思ったけれど、黒く塗りつぶされている処理とかが面倒くさくなった出ござる。
そもそも２つの領域はconvexという話なので、
WWWWWWBBBBBという塗り方か、
BBBBBBWWWWWという塗り方しかあり得ないわけです。
よって、領域の左側が白くなるパターン数を計算＋領域の左側が黒くなるパターン数を計算すれば良い。
左側の白のパターン数は、
dp[x][y][k]…x行目の左からy個が白であるパターン数。ただし、k=0は白と黒の境界が垂直。k=1は境界が左下の向き、k=2は境界が右下の向き。
というdpを更新する事で、
50*50*3くらいのオーダーで計算できる。
最後に、左右対称な配置は重複して数えてしまうことから、そこの帳尻をあわせて終わり。

コード
    int mod = 1000000007;
    int size;
    int ssize;
 int countWays_int( vector<string> grid ){
    // count white left patterns
    int dp[52][52][3];// dp[i][j][k]...i th row with j whites in the left ,k=0...|  [k]=1.../ k=2...rev.of./
    memset( dp, 0 , sizeof(dp));
    int start=0;
    int goal=ssize;
    // [start,goal] is the valid nums
    for( int i = 0 ; i < ssize; i++ ){
      if( grid[0][i] == 'W' ) start = i+1;
      if( grid[0][i] == 'B' && goal == ssize ) goal =i;
    }
    if( start > goal ) return 0;
    for( int x = start;  x <= goal ;x++ ){
      dp[0][x][0] = 1;
    }
      for( int k = 0 ; k <= ssize; k++ ){
        cout << dp[0][k][0] << ", ";
      }
      cout << endl;
    for( int x = 0 ; x+1 < size; x++){
      // update dp[x+1][y]
      start =0;
      goal = ssize;
      for( int i = 0 ; i < ssize; i++ ){
        if( grid[1+x][i] == 'W' ) start = i+1;
        if( grid[1+x][i] == 'B' && goal == ssize ) goal =i;
      }
      cout << start << "-"<< goal << endl;
      if( start > goal ) return 0;
      for( int y = start; y <= goal; y++ ){
        // set dp[1+x][y][0]
        ll tmp =0;
        for( int k = 0 ; k < y; k++ ){
          tmp += dp[x][k][0];
          tmp += dp[x][k][1];
          tmp %= mod;
        }
        tmp += dp[x][y][1];
        tmp %= mod;
        dp[1+x][y][1] = tmp;
        tmp = 0;
        for( int k = ssize; k > y ; k-- ){
          tmp += dp[x][k][0];
          tmp += dp[x][k][2];
          tmp %= mod;
        }
        tmp += dp[x][y][2];
        tmp %= mod;
        dp[1+x][y][2] = tmp;
        dp[1+x][y][0] = dp[x][y][0];
      }

      for( int k = 0 ; k <= ssize; k++ ){
        cout << "("<<dp[1+x][k][0] << ", "<<dp[1+x][k][1] << ", "<< dp[1+x][k][2] << ") ";
      }
      cout << endl;
    }
    ll res = 0;
    for( int y = 0 ; y <= ssize; y++ ){
      for( int k = 0 ; k < 3 ; k++ )
      res +=dp[size-1][y][k];
      res %= mod;
    }
    return res;
    
  }
  int countWays(vector <string> grid) {
    ll result=0;
    size = grid.size();
    ssize= grid[0].size();
    result+=(countWays_int(grid));
    result%=mod;
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < ssize; j++ ){
        if(grid[i][j] == 'W' ) grid[i][j] = 'B';
        else if( grid[i][j] == 'B' )grid[i][j] = 'W';
      }
    }
    result += countWays_int(grid);
    result %= mod;
    cout << result << endl;
    {
      for( int i = 0 ; i <= size; i++ ){
        // i top rows are all white, size-i rows are all black
        bool ok = true;
        for( int x = 0 ; x < size ; x++ ){
          for( int y = 0 ; y < ssize; y++ ){
            if( x < i && grid[x][y] == 'B' ){
              ok = false;
              break;
            }
            if( x >= i && grid[x][y] == 'W' ){
              ok = false;
              break;
            }
          }
          if( !ok ) break;
        }
        if( ok ){
          cout << "i" <<i << endl;
          result += mod-1;
          result %= mod;
        }
      }
    }
    {
      for( int i = 0 ; i <= size; i++ ){
        // i top rows are all black, size-i rows are all white
        bool ok = true;
        for( int x = 0 ; x < size ; x++ ){
          for( int y = 0 ; y < ssize; y++ ){
            if( x < i && grid[x][y] == 'W' ){
              ok = false;
              break;
            }
            if( x >= i && grid[x][y] == 'B' ){
              ok = false;
              break;
            }
          }
          if( !ok ) break;
        }
        if( ok ){
          cout << "i" <<i << endl;
          result += mod-1;
          result %= mod;
        }
      }
    }
    {
        // i top rows are all black, size-i rows are all white
        bool ok = true;
        for( int x = 0 ; x < size ; x++ ){
          for( int y = 0 ; y < ssize; y++ ){
            if( grid[x][y] == 'W' ){
              ok = false;
              break;
            }
          }
          if( !ok ) break;
        }
        if( ok ){
          result += 1;
          result %= mod;
        }
    }
    {
        // i top rows are all black, size-i rows are all white
        bool ok = true;
        for( int x = 0 ; x < size ; x++ ){
          for( int y = 0 ; y < ssize; y++ ){
            if( grid[x][y] == 'B' ){
              ok = false;
              break;
            }
          }
          if( !ok ) break;
        }
        if( ok ){
          result += 1;
          result %= mod;
        }
    }
    return result;
  }