スポンサーサイト

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

Yandex.Algorithm 2011 Round 1

2011/05/21 0:00~2:00 (JST)
Yandex.Algorithm 2011 Round 1 の参加記録

上位 200 人が通過。
Round 1 なのにボーダーが高い。

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

結果

A. 2WA, AC (00:23)
B. AC (00:58)
C. 2WA, Hacked
D. -
E. -
Hacks : ±0 (0 success, 0 miss)
Standing : 370/1168
Rating : 18291804


問題

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

A. Domino
2 × 1 のブロックを 4 × n の長方形領域に、重ならず、すきまができないないように敷き詰める。
ブロックは 90 度回転させて、1 × 2 として使ってもいい。
ただし、長方形領域の n-1 個の垂直線のどれについても、少なくとも 1 つのブロックが垂直線を横切るように並べたい。

具体的な並べ方を 1 つ求めよ。
答えがない場合は -1 と出力せよ。

1 ≦ n ≦ 100

B. Embassy Queue
3 種類の窓口 (type_1, type_2, type_3 と書く) がある。
type_i の窓口は k_i 個あり、時間 t_i で 1 人の客を処理できる。
各窓口は一度に高々 1 人の客を処理できる。

客は type_1, type_2, type_3 の窓口の順で手続きをする。
次に進むべき窓口で、空いているものがあれば、直ちにその窓口へ進む。
空いているものがなければ、空くまで待つ。

今、n 人の客の来る時間が分かっている。
「客が入ってきてから手続きが終わるまでの時間」 の最大値を求めよ。

C. Petya and Tree
頂点数 n の二分探索木 T が与えられる。
T のすべての頂点は 0 or 2 個の子をもつことが保障されている。

k 個のキーが与えられる。それぞれのキー key について、以下で定まる期待値を求めよ。

一般的な二分探索木の探索アルゴリズムを使って、T が key を含むかどうかを判定する。
その際、根から葉にいたるパスのうち、ちょうど 1 回だけ間違った方向に進んでしまう。
( 左の部分木に行くべきところを右に行ってしまう。 逆も同様。 )
パス中のどこで間違うかは等確率で決まる。
辿りついた葉に割り当てられた値の期待値が求めたい値。

3 ≦ n ≦105
1 ≦ k ≦105
n 個の頂点に割り当てられた値と k 個のキーの値はすべて相異なる。

D.

E.

解答

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

A.
char alpha(){
static char c='d';
if(c>'z') c='a';
return c++;
}

int main(){
int n; scanf("%d",&n);

string field[4];
if(n==1){
field[0]="a";
field[1]="a";
field[2]="b";
field[3]="b";
}
else if(n==2){
field[0]="aa";
field[1]="bb";
field[2]="aa";
field[3]="bb";
}
else{
field[0]="aac";
field[1]="bbc";
field[2]="caa";
field[3]="cbb";
for(int i=4;i<=n;i++){
if(i%2==0){
field[0]+=field[0][i-2];
field[1][i-2]=alpha();
field[1]+=field[1][i-2];
field[2]+=alpha();
field[3]+=field[2][i-1];
}
else{
field[0]+=alpha();
field[1]+=field[0][i-1];
field[2]+=field[2][i-2];
field[3][i-2]=alpha();
field[3]+=field[3][i-2];
}
}
}

rep(i,4) puts(field[i].c_str());

return 0;
}

n = 1, 2 のときは、例外処理。
n = 3 のときは、
aac
bbc
caa
cbb
として、一般の n = k (≧ 4) は n = k-1 から構成するようにした。
たとえば、n = 4 は
aacc
bbdd
caae
cbbe
みたいな感じ。

あまり賢い解法ではない。

B.
int main(){
int k[3],t[3],n,c[100000];
rep(i,3) cin>>k[i];
rep(i,3) cin>>t[i];
cin>>n;
rep(i,n) cin>>c[i];

ll ans=0;
int cnt[3]={};
queue<int> wait[3];
priority_queue< pair<ll,pii> > pq;
rep(i,n) pq.push(mp(-c[i],mp(i,0)));
while(!pq.empty()){
pair<ll,pii> a=pq.top(); pq.pop();
ll tm=-a.first;
int id=a.second.first;
int type=a.second.second/2,io=a.second.second%2;

if(io==0){ // in
if(cnt[type]<k[type]){
cnt[type]++;
pq.push(mp(-(tm+t[type]),mp(id,2*type+1)));
}
else{
wait[type].push(id);
}
}
else{ // out
cnt[type]--;
if(type==2){
ans=max(ans,tm-c[id]);
}
else{
pq.push(mp(-tm,mp(id,2*type+2)));
}

if(!wait[type].empty()){
int id2=wait[type].front(); wait[type].pop();
pq.push(mp(-tm,mp(id2,2*type)));
}
}
}

cout<<ans<<endl;

return 0;
}

面倒なシミュレーション。
DP 解もあるらしいけど、よくわからなかった。

窓口が空くのを待っている人を別の queue で管理することで、多少書きやすくなった。

客のデータを構造体でまとめたりしてないので、可読性はとても低い。
多分、自分以外は読めない。1 週間もたてば自分にも読めなくなる。

C. (時間外)
int n,key[100000];
vector<int> tree[100000];

int l_min[100000],l_max[100000],r_min[100000],r_max[100000];

void dfs1(int u){
if(tree[u].empty()){
l_min[u]=l_max[u]=r_min[u]=r_max[u]=key[u];
return;
}

int vl=tree[u][0]; dfs1(vl);
int vr=tree[u][1]; dfs1(vr);

l_min[u]=l_min[vl];
l_max[u]=r_max[vl];
r_min[u]=l_min[vr];
r_max[u]=r_max[vr];
}

double ex[100000];

void dfs2(int u,double sum,int m){
if(tree[u].empty()){
ex[u]=sum/m;
return;
}

int vl=tree[u][0]; dfs2(vl,sum+r_min[u],m+1);
int vr=tree[u][1]; dfs2(vr,sum+l_max[u],m+1);
}

int main(){
int root;
scanf("%d",&n);
rep(u,n){
int p; scanf("%d%d",&p,key+u); p--;
if(p==-2) root=u;
else{
tree[p].push_back(u);
if(tree[p].size()==2){
int &v1=tree[p][0],&v2=tree[p][1];
if(key[v1]>key[v2]) swap(v1,v2);
}
}
}

dfs1(root);
dfs2(root,0,0);

static pii order[100000];
rep(u,n) order[u]=make_pair(key[u],u);
sort(order,order+n);

int q; scanf("%d",&q);
while(q--){
int k; scanf("%d",&k);
pii *p=lower_bound(order,order+n,make_pair(k,-1));
if(p==order+n || !tree[p->second].empty()) p--;

printf("%.15f\n",ex[p->second]);
}

return 0;
}

[ 2011/09/05 追記 ]

Ignat さんの解説を見ながら解いた。

まず、根から DFS して、各頂点について
・ 左の部分木に含まれる最大の値
・ 右の部分木に含まれる最小の値
を求めておく。
O(n) でできる。

再び、根から DFS して、各葉について
・ その葉に到達するようなクエリに対する期待値
を求める。
先の前処理により、これも O(n) でできる。

以上で準備ができたので、各クエリを処理していく。
各クエリに対して、「二分探索木が正しく動いたときに key が二分探索木のどの葉に到達するか」 がわかれば、先の前処理の結果より答えが即座に求められる。
これは、二分探索を使えば O(log n) でできる。

合計の計算量は O(n + k log n) となる。

D.



E.



感想

Petr と同じ部屋!!

A.
なぜか n = 1 で Impossible としていて 1WA.
1 byte のタイプミスでもう 1WA.
この辺りから、すでにダメな感じはしてた。

B.
問題文をがんばって読んで、がんばって実装する。
バグも少なく、思ったより早く書きあがった。

C.
与えられる二分探索木は必ずしも平衡していない。
なので、単純に全部のルートを調べる方法では、最悪 O(kn) かかってしまい TLE になる。
わからないので、一応、TLE するコードを投げてみたら Petr に一瞬で落とされた。
ずっと C を考えていたので、Hack する余裕はなかった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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