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

正月休みにSRM602も復習しました。
この回は寝ぶっちしたわけですが、多分参加してたらレート落ちたと思います。Easy手間取りすぎ。

Easy TypoCoderDiv1

問題

うろ覚えなので本質を失わない程度に適当にかきます。
i番目のコンテストに勝利するとレートがD[i]上がり、敗北するとレートがD[i]下がるようなプロコンを考える。
プレイヤーの初期レートはXで、レート2200を超えると赤コーダーになる(確か本当は違う色だったけど忘れた)
プレイヤーは謙虚なので、2回連続で赤コーダーに居とどまるような勝ち方はしないものとする。
なお、レートは負の値になることはない。
与えられたD,Xに対して、プレイヤーが赤コーダと非赤コーダの行き来を最大何回おこせるかを答えよ

考えたこと

連続して赤コーダーに居留まることがない、っていう条件の意味がわからずテストケースと結構にらめっこした。
結局、赤コーダになった後は確実に黄色コーダー以下におちないといけないってことだから、
そのような条件を満たす時にしか赤コーダにはなれないってことだとわかる。
とは言え、その枝刈りをしたとしても勝ち負け全パターン探索は2^size(D)=2^50の探索だから無理ゲー
ゴニョゴニョ考えたけど結局のところi番目のコンテスト終了時のレートがkであるパターン数をdp[i][k]で管理すれば
50*2200の探索空間に収まりそうだな、って結論づけた。

コード

レートが負になる場合とか色々考慮忘れたりちんたら実装してたら妙に時間を食った。

int getmax(vector <int> D, int X){
    memset(dp,-1,sizeof(dp));
    int size = D.size();
    dp[0][X] = 0;
    int ans = 0;
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < 2200; j++ ){
        if( dp[i][j] != -1 ){
          if( j+D[i] < 2200 ){
            dp[i+1][j+D[i]]=max(dp[i+1][j+D[i]],dp[i][j]);
          }
          if( j+D[i] >= 2200 && i+1 == size ){
            ans= max( ans, dp[i][j]+1 );
          }
          if( j+D[i] >= 2200 && i+1 < size && j+D[i]-D[i+1] < 2200 ){
            dp[i+2][max(0,j+D[i]-D[i+1])]=max(dp[i+2][max(0,j+D[i]-D[i+1])],dp[i][j]+2);
          }
          dp[i+1][max(0,j-D[i])]=max(dp[i+1][max(0,j-D[i])],dp[i][j] );
        }
      }
      /*
      for( int j = 0 ; j < 2200; j++ ){
        if(dp[i][j] != -1 ){
          cout << "dp["<<i<<","<<j<<"]="<<dp[i][j] << ", ";
        }
      }
      cout << endl;*/
    }
    for( int j = 0 ; j < 2200; j++ ){
      /*
        if(dp[size][j] != -1 ){
          cout << "dp["<<size<<","<<j<<"]="<<dp[size][j] << ", ";
        }
        */
      ans =max(ans,dp[size][j]);
    }
  return ans;
  }

計算量は考察にも書いたとおりコンテスト数＊レート範囲。この場合50*2000

Medium PilingRectsDiv1

2*N枚の長方形の紙がある。それぞれ縦・横の長さは以下のように規定される
i番目の横幅=XS[i] if i

何も見ないで考える事

点数の定義を重複部ではなくて表面積の和集合の面積みたいに勘違い。はああなにそれ無理ゲーってなってた。

復習フェーズ

ここでチラリとkmjpさんのブログを拝見(http://kmjp.hatenablog.jp/entry/2013/12/29/1000)。
勘違いには気づいたもののN枚の紙の最適な並べ方が理解できずに「？？？」となった。
ここでwriterであるsnukeさんのブログも発見(http://snuke.hatenablog.com/entry/2013/12/29/040056)

とりあえず、全部横長の長方形になるように回転しておきます。(ちょっと考えると重ねる時には向きをそろえた方が有利なことが分かるので)

ﾅ､ﾅﾝﾀﾞｯﾃｰ！　というわけで改めて考えなおしてみると、確かにその通りだった。

以下、ラフな説明。
2枚の紙(H0,W0)と(H1,W1)を重ねることを考える。(H0H1の時を考えると、向きを変えずに重ねたばあいはH1*W0の重複部分がつくれる。
向きを変えた場合は、横幅：H0=i)]で、 $(H_y,W_y)$ がSに属する物が存在する。
ここで、もし $(H_x,W_x)\in S,(H_y,W_y)\notin S$ を $(H_x,W_x)\notin S,(H_y,W_y)\in S$ に入れ替えると、
$min_{k\geq i, k\in S} H_k$ の値を変えずして $min_{k\notin S}H_k$ の値を増やす(または不変)ことができるとわかる。
　値が増えるのなら矛盾だし、不変だとしても、これを延々と繰り返すことで添字i以上の高さベストNの集合をとった場合のTが最大点数を持つと言える。
(b) $min_{k\geq i, k\in S} H_k>min_{k\notin S}H_k$ の時
(a)とほぼ同様なので略。ただこの場合は高さワーストNの場合に行き着く。

(2)でTにワーストNを持ってくるケースというのは、S側に高さベストNが集まっている状態であるといえる。
つまり結局、
あるiについて、
添字i以上の高さベストNを持ってきた時の高さ最小値(Hとする)* W_i + 第一項以外の長方形の高さの最小値(hとする)*第一項以外の横幅の最小値(wとする)
をi=0〜Nに関して求めて、その最大値を答えれば良いとわかる。

では、どのように実装するか、という話。
Nが最大10^5なので、log N以下の速度でH,h,wが求められればOKである。

Hの求め方：i=Nの時に優先度付きキューの二分木による実装を作っておいて、H_iの値に応じて最小値をpop+H_iをインサート、みたいな形でlog N時間で計算可。実装ではsetを用いた。
hの求め方：hlist[m]= $min_{k\leq m} H_m$ という配列を用意。ベストNからあぶれた添字の最大値Kを保存しておけばh=hlist[K}と表せる。
wの求め方：i=0以外の場合はW_0に等しい。i=0の時に限ってなら、10^5の時間かけてwを求めるのも問題なし。

コード

 long long getmax(int N, vector <int> XS, vector <int> YS, int XA, int XB, int XC, int YA, int YB, int YC){
    vector<pair<ll,ll> > Rects;
    int size = XS.size();
    long long X=XS[0];
    long long Y=YS[0];
    for( int i = 0 ; i < 2*N ; i++){
      if( i < size ){
        Rects.push_back( make_pair(max(XS[i],YS[i]),min(XS[i],YS[i])) );
        X=XS[i];
        Y=YS[i];
      }
      else{
        X=(X*XA+XB)%XC+1;
        Y=(Y*YA+YB)%YC+1;
        Rects.push_back( make_pair(max(X,Y),min(X,Y)) );
      }
    }
    sort(Rects.begin(),Rects.end());

    long long minHeight[2*N];
    minHeight[0] = Rects[0].second;
    for( int i = 1 ; i < 2*N ; i++ ){
      minHeight[i] = min(minHeight[i-1],Rects[i].second);
    }
    set<pair<ll,int> > S;
    bool vis[N*2];
    memset( vis, false, sizeof( vis ) );
    for( int i = N ; i < 2*N; i++ ){
      S.insert( make_pair( Rects[i].second,i) );
      vis[i] = true;
    }
    long long ans = S.begin()->first*Rects[N].first + minHeight[N-1]*Rects[0].first;
    //cout << S.begin()->first <<"*"<<Rects[N].first<<"+"<<minHeight[N-1]<<"*"<<Rects[0].first<<endl;
    int ind = N-1;
    for( int j = N-1; j >= 0 ; j-- ){
      if( Rects[j].second > S.begin()->first ){
        vis[j]=true;
        vis[S.begin()->second]=false;
        ind = max( ind, S.begin()->second );
        S.erase( S.begin() );
        S.insert( make_pair(Rects[j].second, j) );
        ans = max(ans, S.begin()->first*Rects[j].first + minHeight[ind]*Rects[0].first);
        //cout << S.begin()->first <<"*"<<Rects[j].first<<"+"<<minHeight[ind]<<"*"<<Rects[0].first<<endl;
        if( j == 0 ){
          int minind =0;
          while( vis[minind]==true ) minind++; 
          ans = max(ans, S.begin()->first*Rects[j].first + minHeight[ind]*Rects[minind].first);
          //cout << S.begin()->first <<"*"<<Rects[j].first<<"+"<<minHeight[ind]<<"*"<<Rects[minind].first<<endl;
        }
      }
    }
    return ans;
  }

感想

本番に出されてこれは解ける気が全くしないというか、
向きを揃えることが分かったとしても、ベストN or ワーストNを利用するっていう所にまず気づける気がしなかった。
そこに気付いたならば、優先度付きキュー使うってのに気づくことはできそうな…気もするが、
iをNの方から走査させるって所が少しトリッキー（よくあるとはいえ）だし、ノーヒントなら気づけないかも知れない。
さらに、優先度付きキューを使うっていうのがわかってからも、hとかwを求めるために配列を付け加える必要が出て大変だった。
落とし穴の多い問題、というイメージ。