SRM610

Codeforces２回位参加記書いてないけどSRMがあったので先にそっちを。
２完最弱でしたが550を本番に解けたので頑張った方かと思います。
多分Div1で２連続２完って初なんじゃなかろうか。

Level	ProblemName	Status	Point
Easy	TheMatrix	Passed System Test	162.87
Medium	AlbertoTheAviator	Passed System Test	181.35
Hard	????	Unopened	0.0

Easy TheMatrix

問題

0か1でうめつくされたテーブルを入力として与えるので、テーブル内に含まれる
01010101
10101010
みたいな、チェス盤観たいな配置になっている長方形の最大面積を答えよ

考えたこと

とりあえず、長方形の内部にセル(x1,y1)と(x2,y2)が含められるか否かは、(xi+yi+table[xi][yi])%2が(i=1,2)で等しいかどうかを見れば良い
また、テーブルの辺Nの最大が100なので長方形領域の左端座標×右端座標を与える全探索は計算量N^4で危うい気がする。
ってことは、開始地点の座標(a,b)と長方形の高さkを与えた時に横幅がさっと求められれば良い。
最初はDP?とか思って色々検討したけど上手くいかず。
と言うか、(x,y)から(x,Y)までが同じ長方形に含めることが可能、というY>yの値をnext[x][y]という配列に保存するとすれば、
(a,b)を決める→kを1から順に増やしつつ、next[x][y]を観ながら横幅決定
なんて流れにすることで計算量をN^3にすることができる
next[x][y]はxを固定してyの大きい順にごりごり計算すればN^2の計算量で求まる。

…ここまで考えるために２０分位時間使った悲しみ。

コード

   int MaxArea(vector <string> board){
      int h = board.size();
      int w = board[0].size();
      int bit[h][w];
      memset( bit, 0 , sizeof(bit));
      for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++ ){
          bit[i][j]= (i+j+board[i][j])%2;
        }
      }
      int next[h][w];
      memset( next, 0, sizeof(next) );
      for( int i = 0 ; i < h ; i++ ){
        next[i][w-1] = w-1;
        for( int j = w-2; j >= 0 ; j-- ){
          if( bit[i][j] == bit[i][j+1] ){
            next[i][j] = next[i][j+1];
          }
          else{
            next[i][j] = j;
          }
        }
      }
      /*
      for( int i =0  ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++ ){
          cout << bit[i][j];
        }
        cout << endl;
      }
      for( int i =0  ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++ ){
          cout << next[i][j];
        }
        cout << endl;
      }*/
      int ans = 0;
      for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w; j++ ){
          int b = bit[i][j];
          int curw = next[i][j]-j+1;
          int curans = curw;
          int k = i;
          while( k < h && bit[k][j] == b ){
            curw = min( curw, next[k][j]-j+1 );
            curans = max( curans, curw*(k-i+1) );
            k++;
          }
          ans = max(ans,curans);
        }
      }
      return ans;

  }

Medium AlbertoTheAviator

問題

燃料duration[i]を消費して後に燃料refuel[i]だけ獲得できるミッションが与えられる。(refuel[i]

考えたこと

ミッション遂行可能ならduration-refuelの小さい順にミッションしてけばいいんでないの？
この値が同じ場合はdurationの大きい順のほうがfuel不足でミッションできないというケースを弾けそう。
→試しに書いてみる
→テストケース 9 {4,6} {0,1}で落ちることが判明。(duration=4,refuel=0を先に実行してしまうと残り燃料が5になりduration=6,refuel=1を実行不可能)良心的なテストケースだ。
→durationの総和-refuelの総和がF以下となるような部分集合を取れば燃料切れを起こさないミッションの順番が作れるとか？
→100 {101} {1}で落ちる。
→そもそもそんなケースってdurationがFより大きい場合くらいしか無い…？　ならそれを弾くだけで良いのだろうけど。。。
→ちょっとサンプルを弄りながら考えてみるけどサラッと反例が作れない。
→コード書いたらサンプル全部通る
→悩んだけど550だし一端提出する
→しばらくして 9 {5,6} {1,1}で落ちることに気づく
→うーん、じゃあDPとかですか？ i番目のミッションまでで燃料をf残した状態を作る最大ミッション数をdp[i][f]にする50*5000のテーブルとか。
→durationの大きい順にミッションを舐めていると 10 {8,4} {0,2}で落ちるしうーん。。。
…
……
………
→ふと、終状態から考えてみる。 9 {4,6}{0,1}は2が解だけど9 {5,6}{1,1}は1が解になるのは、最終的に燃料が0になるから。と言うか、燃料が0になる時、直前でrefuelが非ゼロのミッションはできない。
→…ってことは、燃料fの直前にはrefuel[i]<=fのミッションしか実施できないってこと。
→refuel[i]<=fのミッションの中で燃料をあまり使わないミッションを選べば良い。これを任意の終わり状態について計算。

→サンプル通ったし9{4,6}{0,1}と9{5,6}{1,1}もちゃんと想定通りの解が帰ってくる。やったね。

コード

int MaximumFlights(int F, vector <int> duration, vector <int> refuel){
     int size = duration.size();
     vector<pair<int,int> > vec;
     for( int i = 0 ; i < size; i++ ){
      vec.push_back( make_pair( refuel[i],duration[i] ));
     }
     sort( vec.begin(),vec.end());
     int ans =0;
     for( int i = 0 ; i <= F ; i++ ){
      //cout << "start "<<i<<endl;
      int curans = 0;
      int f = i;
      int ind = 0;
      priority_queue< int > q;
      while( ind < size && vec[ind].first <= f ){
        //cout << vec[ind].first <<"-"<<vec[ind].second<<endl;
        q.push( vec[ind].first-vec[ind].second );
        ind++;
      }
      while( !q.empty () ){
        int cur = q.top();
        q.pop();
        f-=cur;
        if( f > F ) break;
        //cout << f << endl;
        curans++;
        while( ind<size && vec[ind].first <= f ){
          q.push( vec[ind].first-vec[ind].second );
          ind++;
        }
      }
      //cout <<"try"<<curans<<endl;
      ans =max(ans,curans);
     }
     return ans;
}