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

beet's soil

競プロのことなど

SRM 702 Div2

珍しく人道的な時間だったので講義があったけど参加しました

【250- TestTaking】

概要

二択のテストの回数と真と答えた回数と実際の真の個数が与えられるので、取りうる最大の正答数を求める。

解法

真で取れる正答数と偽で取れる正答数の和が答えになる
O(1)

int findMax(int questions, int guessed, int actual) {
  return min(guessed,actual)+min(questions-guessed,questions-actual);
}


【500- GridSort】

概要

n*mのグリッドに1~n*mまでの数が書かれているので、行同士か列同士を何回でもスワップすることで順番通りにできるかを判定する。

解法

スワップの順番はお互いに影響を及ぼさないので、1から順番に正規の場所に移動していき、最終的に順番通りになっているかを確認すれば良い
O(N*M*(N+M))

string sort(int n, int m, vector <int> grid) {
  int i,j,k;
  bool f=true;
  for(k=1;k<=n*m;k++){
    int x=0,y=0,ay=(k-1)/m,ax=(k-1)%m;
    for(i=0;i<n;i++){
      for(j=0;j<m;j++){
	if(grid[i*m+j]==k){
	  x=j;y=i;break;
	}
      }
    }
    for(i=0;i<n;i++) swap(grid[i*m+x],grid[i*m+ax]);
    for(j=0;j<m;j++) swap(grid[y*m+j],grid[ay*m+j]);
  }
  for(i=0;i<n*m;i++) f&=(grid[i]==i+1);
  return (f?"Possible":"Impossible");
}


【1000- SubsetSumExtreme】

概要

N個のブロックとM個のサイコロが与えられる。サイコロを振って出た目の数といくつかのブロックの大きさの和が一致するような時、それらのブロックを取り除くことができる。取り除くことができない場合、残っているブロックの大きさの総和がスコアになる。和が一致してさえいれば取り除き方は自由なので、スコアが最小となるように最適な戦略を取った時の期待値を求める。

解法

和を求める再帰関数と最小値を求める再帰関数を交互に呼ぶ。
O((2^N)*N*M)

  vector <int> b,x;
  double memo[20][1<<15]={};
  double p[20];
  const double inf = 1<<28;
  #define EPS 1e-10
  double rec2(int d,int bi,int y){
    double res = inf;
    if(y==0) return rec(d+1,bi);
    if(y<0) return inf;
    for(int i=0;i<b.size();i++){
      if((bi>>i)&1) res=min(res,rec2(d,bi-(1<<i),y-b[i]));
    }
    return res;
  }
  
  double rec(int d,int bi){
    if(memo[d][bi]>=0) return memo[d][bi];
    int i,sum=0;
    double res=0;
    for(i=0;i<b.size();i++) if((bi>>i)&1) sum+=b[i];
    for(i=0;i<x.size();i++){
      double m = rec2(d,bi,x[i]);
      if(m<inf+EPS) res+=m;
      else res+=p[d]*sum;
    }
    return  memo[d][bi] = res;
  }
  
  double getExpectation(vector <int> block, vector <int> face) {
    b=block;
    x=face;
    for(int i=0;i<20;i++)
      for(int j=0;j<(1<<15);j++)
	memo[i][j]=-1;
    p[0]=1;
    for(int i=0;i<20-1;i++) p[i+1]=p[i]/x.size();
    return  rec(1,(1<<b.size())-1) ;
  }

TopCoderはreturnするというのを忘れていて標準入出力したり、
return res=memo[d][bi] としたり、
ローカルのテストは落ちるのにアリーナのテストは通ったりしたり、
EPS足してはいけないのに足してみたり、
色々ミスったけどSystemTest通ってしまってびっくりした。
(inf+EPSが情報落ちでinfになっていなかったら落ちてた)

【全体】
1085 -> 1258
ルーム内2位でした。
なんとかDiv1に戻れたのでまたすぐ落ちたりしないように頑張りたいです。
新しいGoogle翻訳は神