SRM623

Google Code JamでTシャツ圏外だったりCodeForcesでDiv2に落ちたりTCO Marathon Match全く話にならなかったり最近負け続きである。
少しでも復習とかちゃんとやっていかないと駄目ですねこりゃ。と思っての更新。参加記執筆速度も多分上げたほうが良いんだろうな。
とりあえず有給とってのSRM回位はちゃんと書きましょう。ちなみにレートは微増。有給とってレート下がるとさすがにテンション下がるので少しでも上がってよかった。

Level	ProblemName	Status	Point
Easy	UniformBoard	Passed System Test	227.30
Medium	CatchTheBeat	Opened(Practiced)	0.0
Hard	AliceAndFriends	Unopened	0.0

Easy

問題

正方形のマス目があり、各セル上に林檎とナシが置かれてたり置かれてなかったりする。
プレイヤーはK回(所与の値)以内の果物の移動(果物をあるセルから取り出し、空セルへと移動させる操作）によって、
林檎で敷き詰められた長方形の面積を最大化したい。最大の面積を答えよ。

考えたこと

マス目の長さ最大が20とかだし普通にあり得る長方形領域を愚直な探索させればいいんじゃないか？
ある長方形領域が与えられたときに、その中を林檎で敷き詰めるためには、各セルについて
林檎がある：何もしないでおｋ
空セル：何処かから林檎をもってくる１ステップ必要（長方形の面積＜林檎の個数ならそのような林檎は必ず存在）
ナシがある：ナシをどこかにどける＆林檎を持ってくるの２ステップ必要（空セルがどこか一つあれば可能な操作であることに注意)
というステップ数を加算すれば求められる。
領域全列挙が20^4でステップ数の計算が20^2、正味20^6位だけど 20^6=6.4*10^7だからなんとかなるっしょ

コード

   int getBoard(vector <string> board, int K){
     int size = board.size();
     int n_apple=0;
     bool possible = false;
     for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < size; j++ ){
        if( board[i][j] == '.' ) possible = true;
        if( board[i][j] == 'A') n_apple++;
      }
     }
     cout << n_apple << endl;
     int ans = 0;
     for( int height = 1 ; height <= size; height++ ){
      for( int width = 1; width <= size; width++){
        int area = height*width;
        if( area > n_apple ) continue;
        for( int x = 0 ; x+height-1 < size; x++ ){
          for( int y = 0 ;y+width-1 < size; y++ ){
            int curK = 0;
            for( int dx = 0 ; dx < height; dx++ ){
              for( int dy = 0 ; dy < width ; dy++ ){
                int curX = x+dx;
                int curY = y+dy;
                if( board[curX][curY] == 'A' ) continue;
                if( board[curX][curY] == 'P' ){
                  if( possible ){
                    curK += 2;
                  }
                  else{
                    curK += 5000;
                  }
                }
                if( board[curX][curY] == '.' ){
                  curK ++;
                }
              }
            }
            //cout << height << ", "<< width << ", "<< x <<", "<<y<< ", "<< curK << endl;
            if( curK <= K ){
              ans = max(ans,area);
            }
          }
        }
      }
     }
     return ans;
  }

Medium CatchTheBeat

問題

2次元座標においてy=0の直線を1秒距離1の速度で移動するプレイヤーと
x[0]=x0-offset,x[i+1]= ((x[i]+offset)*a+b % mod1)-offset
y[0]=y0, y[i+1]=(y[i]*c+b) % mod2
によって計算可能な果物の初期位置(x[i],y[i])が与えられる。
果物は1秒にy軸と水平に1だけ落ちるとする。
プレイヤーは巧みに移動しながら果物の回収量を最大化したい。

考えたこと

移動可能なところに枝張って最大流とかにする的何か？
いやそんなことないな。っていうかノード数500000ってかなりきつくね。
何とかして NlogNくらいで計算しろってことだとは思うけど…
(x[i],y[i])をとった後に取れる果物の範囲って y-x >=(y[i]-x[i]) かつ y+x >= (y[i]+x[i])の範囲なのだが、
これを活かすことはできるだろうか…十分大きなy座標におけるこの区間の重複を数えたりすればいいのか？
→試しに書いてみたけど全然違うわ。アカンわこれ。

復習

一位だったmsg555さんのコードを読んだ。y-xとy+xを使うという着想は割りと良かったらしい。
ちょっとだけ一般化を意識した書き方をすると、今回の問題は、
各果物iについてパラメタAi(=y-x),Bi(=y+x)という値が計算でき、
Ai<=AjかつBi<=Bjだった時のみ果物i,jは連続取得可能とした時、最大取得果物数を答えるということ。

では肝心の解き方については、まず各果物について(A,B)を計算してソートさせることで、
i番目の果物とj番目の果物はiB_(k+1), dp[k][p-1]<=B_(K+1) )
dp[k+1][p]= dp[k][p] otherwise
となる。
これはvector構造とupperbound関数を使ってlogNのオーダでupdate可能である。
よって、これを繰り返していって最終的なdp[last]のサイズが解となる。

コード

   int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset){
     long long x[n];
     long long y[n];
     x[0]=x0;
     y[0]=y0;
     for( int i = 1 ; i < n ; i++ ){
      x[i] = (x[i-1]*a+b)%mod1;
      y[i] = (y[i-1]*c+d)%mod2;
     }
     for( int i = 0 ; i < n ; i++ ){
      x[i]-=offset;
     }
     vector<pair<int,int> > vs;
     for( int i = 0 ; i < n ; i++ ){ if( y[i] >= abs(x[i]) )vs.push_back(make_pair(y[i]+x[i],y[i]-x[i])); }
     sort(vs.begin(),vs.end());
     vector<int> V;
     for( int i = 0 ; i < (int)vs.size() ; i++ ){
      vector<int>::iterator it =  upper_bound(V.begin(),V.end(),vs[i].second);
      if( it == V.end() ) V.push_back(vs[i].second);
      else *it = vs[i].second;
     }
     return V.size();

  }

考察

正直これ今後類問が出ても全然解ける気がしないけど…
二つのパラメタが両方優位の時だけ更新、みたいなモデルを考えるのは微妙に汎用性あるのかもしれないので、頭の片隅には入れておきたい気がする。