スポンサーサイト

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

Yandex.Algorithm 2011 Qualification 2

2011/05/07 0:00~2:00 (JST)
Yandex.Algorithm 2011 Qualification 2 の参加記録

Qualification Round は前回で通過したけど、そういう人たちも Rated で参加できるということで参加。

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

結果

A. WA, AC (00:09)
B. Hacked, AC (01:23)
C. Skipped, AC (01:51)
D. -
E. -
Hacks : ±0 (1 success, 2 miss)
Standing : 320/2197
Rating : 17371829


問題

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

A. Double Cola
Sheldon, Leonard, Penny, Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny, Rajesh, Rajesh, Howard, Howard, Sheldon, Sheldon, Sheldon, Sheldon, Leonard, ...
の順でコーラを飲む。 (連続で飲む回数が 1, 2, 4, 8, ... と増えていく)
n 回目にコーラを飲むのは誰か?

1 ≦ n ≦ 109

B. Sets
いくつかの相異なる自然数を n 個の空でない集合にわける。
さらに、この n 個の集合から 2 つを選んで n(n-1)/2 個の和集合を作る。
n(n-1)/2 個の和集合が与えられたとき、元の n 個の集合を復元せよ。
答えが複数あるときはどれを答えてもよい。

2 ≦ n ≦ 200
2 ≦ 元の集合の要素数 ≦ 200
1 ≦ 使われている自然数の値 ≦ 200

C. General Mobilization
n 頂点の根付き木が与えられる。各辺には容量がついている。

n 人の人がいて、最初、各頂点に 1 人ずつ割り当てられている。
各人にはそれぞれ異なる優先順位がついている。

各時間ステップにおいて、
各人は、根に向かって、1 つの辺を移動する。
ただし、辺の容量を超える人数は渡れない。辺の容量 C を越える人数が渡ろうとした場合、優先順位の高い C 人が渡ることができる。
渡れなかった人は同じ頂点でとどまる。

各人が根に到達するまでの時間を求めよ。

1 ≦ n ≦ 5000

D. Two out of Three
n 人の客が一列でレジに並んでいる。
それぞれの客のレジ打ちにかかる時間がわかっている。
レジでは 2 人の客を同時に対応することができて、次のアルゴリズムで客を処理する。

1. 列の先頭の 3 人の中から 2 人を選んで、同時にレジに回す。列に 2 人までしかいないときはその人を回す。
2. レジ打ちにかかる時間は、2 人の客のレジ打ちにかかる時間の大きいほうである。 ( レジ打ちは 2 人同時に終了する )
3. 客がいなくなるまで 1. に戻る。

最適な選択をしたときにレジ打ちにかかる合計時間とその選び方を答えよ。

1 ≦ n ≦ 1000
1 ≦ 客 1 人のレジ打ちにかかる時間 ≦ 106

E.

解答

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

A.
int main(){
const char *name[]={"Sheldon","Leonard","Penny","Rajesh","Howard"};

int n; scanf("%d",&n);
queue< pair<int,ll> > qu;
rep(i,5) qu.push(mp(i,1));
for(ll cnt=0;;){
pair<int,ll> a=qu.front(); qu.pop();
int id=a.first;
ll num=a.second;
cnt+=num;
if(n<=cnt){
puts(name[id]);
break;
}
qu.push(mp(id,2*num));
}

return 0;
}

問題文どおりにシミュレーションした。
1 人が飲むコーラの本数は指数関数的に増えていくので、109 という上限でも余裕で間に合う。

B.
int main(){
int n; scanf("%d",&n);
int m=n*(n-1)/2;

if(n==2){
int k,a; scanf("%d",&k);
printf("%d",k-1);
rep(j,k-1){
scanf("%d",&a);
printf(" %d",a);
}
scanf("%d",&a);
printf("\n1 %d\n",a);
return 0;
}

vi id[200];
rep(i,m){
int k; scanf("%d",&k);
rep(j,k){
int a; scanf("%d",&a);
a--;
id[a].pb(i);
}
}

vector< pair<vi,int> > ord;
rep(i,200){
if(id[i].size()>0){
sort(id[i].begin(),id[i].end());
ord.pb(mp(id[i],i));
}
}
sort(ord.begin(),ord.end());

vi res[200];
int idx=0;
rep(i,ord.size()){
if(i>0 && ord[i].first!=ord[i-1].first) idx++;
res[idx].pb(ord[i].second);
}

rep(i,n){
printf("%d",res[i].size());
rep(j,res[i].size()) printf(" %d",res[i][j]+1);
putchar('\n');
}

return 0;
}

n = 2 はコーナーケース。別途処理する。

O(n^3) に収まるように注意すれば、実装方法は色々あると思う。
各自然数がどの和集合に属しているかを全部列挙して、そのパターンが完全に一致する自然数は、同じ (元の) 集合に属しているとした。

C.
struct Edge{
int u,v,w;
Edge(){}
Edge(int U,int V,int W):u(U),v(V),w(W){}
};

vector<Edge> tree[5000];

int t,endcnt,ans[5000];
bool ended[5000];
priority_queue< pii,vector<pii>,greater<pii> > pq[5000];

bool simulate(int u,int parent,int capa){
if(u==0){
while(!pq[0].empty()){
pii a=pq[0].top(); pq[0].pop();
int v=a.second;
ans[v]=t;
endcnt++;
}
}
else{
rep(i,capa){
if(pq[u].empty()) break;
pii a=pq[u].top(); pq[u].pop();
pq[parent].push(a);
}
}

bool end=true;
rep(i,tree[u].size()){
int v=tree[u][i].v,capa=tree[u][i].w;
if(v!=parent && !ended[v]) end&=simulate(v,u,capa);
}
if(end && pq[u].empty()) ended[u]=true;
return ended[u];
}

int main(){
int n; scanf("%d",&n);
int prior[5000];
rep(i,n) scanf("%d",prior+i);
rep(i,n-1){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
u--, v--;
tree[u].pb(Edge(u,v,w));
tree[v].pb(Edge(v,u,w));
}

rep(i,n) pq[i].push(mp(prior[i],i));

endcnt=0;
for(t=0;endcnt<n;t++) simulate(0,-1,-1);

rep(i,n) printf("%d%c",ans[i],i<n-1?' ':'\n');

return 0;
}

O(n2) のシミュレーション。 (もしかすると、O(n2log n) になってるかもしれない)
全部の頂点が一列につながっているようなケースを手元で試してみると 12 秒かかったのに、Codeforces 上では 0.6 秒で終わっていた。
Codeforces サーバーは爆速。自分の PC が遅いだけかもしれないが。

優先順位まわりの処理を書きやすくするために、priority_queue を使った。
また、それ以上先の頂点を調べても人がいないときには、そこで探索を打ち切るような枝刈りを入れた。

D. (時間外)
int n,a[1000],memo[1000][1000],path[1000][1000];

int dfs(int i,int j){
if(i>=n) return 0;
if(j>=n) return a[i];

if(~memo[i][j]) return memo[i][j];

int k=j+1,tmp[3];
tmp[0]=max(a[i],a[j])+dfs(k,k+1);
tmp[1]=max(a[i],a[k])+dfs(j,k+1);
tmp[2]=max(a[j],a[k])+dfs(i,k+1);

int idmin=min_element(tmp,tmp+3)-tmp;
path[i][j]=idmin;

return memo[i][j]=tmp[idmin];
}

void printPairs(int i,int j){
if(i>=n) return;
if(j>=n){
printf("%d\n",i+1);
return;
}

int k=j+1;
if(path[i][j]==0){
printf("%d %d\n",i+1,j+1);
printPairs(k,k+1);
}
else if(path[i][j]==1){
printf("%d %d\n",i+1,k+1);
printPairs(j,k+1);
}
else{
printf("%d %d\n",j+1,k+1);
printPairs(i,k+1);
}
}

int main(){
scanf("%d",&n);
rep(i,n) scanf("%d",a+i);

memset(memo,-1,sizeof memo);

printf("%d\n",dfs(0,1));
printPairs(0,1);

return 0;
}

[ 2011/05/09 追記 ]

解法が思いつかなかったので、Parenti さんのコメントを参考にした。
おもしろい問題。

列の最初の 2 人を固定すると、3 人目も自動的に決まるのがポイント。
この性質から、最初の 3 人の組を状態にするのに O(n2) のメモリで済む。
それに気付けば、あとはシンプルな DP (メモ化再帰)。
ただし、経路復元つき。

E.



感想

A.
1 WA したのは scanf("%lld",&n); としたせい。
%lld が使えない仕様は何とかしてほしい。

B.
多くの例に漏れず、コーナーケースを見逃して Hack されたので、
/* Thank you for debugging :) */
というコメントをいれて再提出した。

C.
自分のコードは TLE で落ちると思っていたので、同じようなことをしてた人に上に書いた最大ケースを投げたら、1 成功 2 失敗だった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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