スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Yandex.Algorithm 2011 Finals

2011/07/15 21:00~23:00 (JST)
Yandex.Algorithm 2011 Finals の参加記録

ファイナルまで残れなかった人も Out of competition として参加できて、Div.1 なら Rating もつくらしい。

Tags : プログラミング Codeforces 未解決

結果

A. -
B. -
C. WA(pretest), AC (01:40)
D. -
E. -
Hacks : ±0 (0 success, 0 miss)
Standing : 38/759
Rating : 17271777


問題

問題セットの原文はここを参照。

A. Domino
大きさ 1 × 2 のドミノが 28 枚ある。
ドミノの配置が指定される。 (どのドミノをどの場所に置くかは自分で決められる。)

ドミノたちの上に 2 × 2 の正方形を 14 個重ならないように置くとき、各正方形内にあるドミノの面の数字が同じになるようなドミノの置き方は何通りあるか?

また、具体的な置き方も 1 つ求めよ。

B. Superset
2 次元平面上の格子点の集合 S が与えられる。

要素数 2×105 以下の点集合 T ( ⊃ S ) で、
T の任意の 2 点 p, q に対して、次の 3 条件のうち少なくとも 1 つが成り立つようなものを 1 つ求めよ。
・ p と q の x 座標は等しい
・ p と q の y 座標は等しい
・ p と q を頂点とする長方形は、(p, q 以外の) T の点を少なくとも 1 つ含む

1 ≦ |S| ≦ 104

C. Winning Strategy
毎年、n 人 1 チームで ICPC に出場する。

同じ選手は 2 回までしか出場できない。
出場経験のない選手は無限にいるとする。

チームに出場経験のある選手が k 人いるとき、その年の勝率が pk であることが分かっている。 (0 ≦ k ≦ n)

最適なチーム編成をするとき、平均勝率の最大値を求めよ。

3 ≦ n ≦ 100
0 ≦ pk ≦ 1
pk は広義単調増加

D.
E.

解答

言語は C++。テンプレはここを参照。

A.


B. (時間外)
struct P{
int x,y;
bool operator<(const P &p)const{ return x!=p.x?x<p.x:y<p.y; }
bool operator==(const P &p)const{ return x==p.x && y==p.y; }
};

void solve(int l,int r,const vector<P> &ps,vector<P> &ans){
if(r<=l) return;

int mi=(l+r)/2;
for(int i=l;i<r;i++) ans.push_back((P){ps[mi].x,ps[i].y});

solve(l,mi,ps,ans);
solve(mi+1,r,ps,ans);
}

int main(){
int n; scanf("%d",&n);
vector<P> ps(n);
rep(i,n) scanf("%d%d",&ps[i].x,&ps[i].y);

sort(ps.begin(),ps.end());

vector<P> ans;
solve(0,n,ps,ans);

sort(ans.begin(),ans.end());
n=unique(ans.begin(),ans.end())-ans.begin();

printf("%d\n",n);
rep(i,n) printf("%d %d\n",ans[i].x,ans[i].y);

return 0;
}

[ 2011/09/05 追記 ]

答えを見た。

分割統治法。
y 軸に平行な直線 L で点集合を 2 分割して、それぞれの superset を考える。
L 上の適切な位置に点を打っておけば、右の部分集合と左の部分集合の間でも、問題文の条件が満たされるようにできる。

発想としては自然なものなので、自力で思いつきたかった。

C.
int main(){
int n; scanf("%d",&n);
double pr[101];
rep(i,n+1) scanf("%lf",pr+i);

static double dp[201][201];
rep(i,201) rep(j,201) dp[i][j]=-1e77;
dp[0][0]=0;
rep(i,2*n+1){ // i 回目の選択
rep(j,2*n+1){ // 控えに過去出場者が j 人いる
rep(k,n+1){ // 過去出場者を k 人使う
if(0<=j+(n-2*k) && j+(n-2*k)<=2*n){
dp[i+1][j+(n-2*k)]=max(dp[i+1][j+(n-2*k)],dp[i][j]+pr[k]);
}
}
}
}

double ans=0;
for(int m=1;m<=2*n;m++) ans=max(ans,dp[m][0]/m);
printf("%.9f\n",ans);

return 0;
}

コンテスト中はほとんどこの問題を考えていた。
というのも、普段から lim とかなんとかは使いまくっているので、この問題が一番手をつけやすいと思えたから。


長くなってわずらわしいので、以下
・ 過去に一度だけ出場経験のある選手を (経)
・ 過去に出場経験がない選手を (新)
と書く。


まず、極限値が問題なので最初の有限回の選択はどうでもいい。
( つまり、最初の 1 回は全員が (新) としないといけないけど、それは気にしなくてよい。 )

(経) が i 人いる状況を考える。
この年の選抜で、
(経) を j 人選ぶと、残り n - j 人の (新) が選ばれるので、(経) の人数は n - 2j 人増える。
( j によって増えたり減ったりする。 )

この選抜を続けていくと、(経) の人数が 0 人となるときが何度でもくる。
すなわち、i 年目に (経) を ai 人選ぶのが最適だとすると、
ai(k) = 0 となるような部分列 {ai(k)} がある。
なぜなら、そうでない選び方は最適解になりえないから。
( これは pi の単調性からいえる。 )

この ik, ik+1 の間を 1 周期として、最適解は周期的になっていると考えていい。
周期的でないとしても、より良い解は得られないから。

実際、1 つめのサンプルの答えは (3p1 + p3)/4 である。


ここまで考察すれば、あとは DP で答えが計算できる。
dp[i][j] := i 回目の選抜後に (経) が j 人残るときの最適解 (の i 倍)
として、
dp[i][0]/i の最大値が答え。

i と j の範囲は余裕を持って 0 ≦ i, j ≦ 2n とすると通った。
( 2n を n とすると pretest すら通らなかった。)

O(n3).

かなり散らかった文章になってしまった。日本語難しい。
これ読んで理解できる人いるのかなぁ...

D.


E.

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。