スポンサーサイト

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

Codeforces Alpha Round #28

日本時間では今日の 0:00~2:00 に催された Codeforces Alpha Round #28 の記録です。
前回の #27 は Div.2 限定で出られなかったので、久しぶりの codeforces でした。

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

[ 問題 ]
今回の問題セットはこんな感じでした。

A. Bender Problem
平面上に刺された n 本の釘と m 本の棒が与えられる。

釘を与えられた順序で結んでできる閉曲線(closed polyline: 閉折れ線?)を考える。
この閉曲線にピッタリ一致するように、棒を添えることができるかを答える。
できる場合は具体的な配置も求める。

ただし、棒の配置は以下の条件をみたさないといけない。
・ 各棒はちょうど1回だけ曲げなければならず、曲げる方向は 90°に限られる。
・ 各棒を曲げる位置と棒の両端は釘のある位置に一致しなければならない。

なお、閉曲線は自己交差していてもよく、また、使わない棒があってもよい。
与えられる閉曲線は、90°以外の角度で曲がっていることはない。

B. pSort
1~n と順に番号付けされた n 個のセルがある。
各セルは値を持っており、その初期値はセルの番号に等しい。
各セルには favorite number という数が定められている。

次の 2 種類の操作
・ セル i の値とセル i + di の値を交換する
・ セル i の値とセル i - di の値を交換する
を行うことができる。操作は何回行ってもいい。
( ただし、di はセル i の favorite number )

具体的な数の順列が与えられるので、上記の操作によってセルの値がその順列に一致しうるかどうかを答える。

C. Bath Queue
D. Do not fear, DravDe is kind
E. DravDe saves the world
読んでない.

[ 解答 ]
言語は C++。include文とusing文は省略。

A. (時間外)
int main()
{
int n,m; cin>>n>>m;
vector<int> seg(n);
int xs,ys; cin>>xs>>ys;
int xb=xs,yb=ys;
for(int i=0;i<n-1;i++){
int x,y; cin>>x>>y;
seg[i]=abs(x-xb)+abs(y-yb);
xb=x,yb=y;
}
seg[n-1]=abs(xs-xb)+abs(ys-yb);

vector<int> rod(m);
for(int i=0;i<m;i++) cin>>rod[i];

int ok=-1;
vector<int> patt[2];
for(int k=0;k<2;k++){
patt[k].resize(n/2);
for(int i=0;i<n/2;i++){
if(k==0) patt[k][i]=seg[2*i]+seg[2*i+1];
else patt[k][i]=seg[2*i]+seg[(2*i+n-1)%n];
}

// check whether it is feasible to make closed polyline
int usedcnt=0;
vector<bool> used(m);
for(int i=0;i<n/2;i++){
for(int j=0;j<m;j++){
if(used[j]) continue;
if(patt[k][i]==rod[j]){
patt[k][i]=j+1;
used[j]=true;
usedcnt++;
break;
}
}
}
if(usedcnt==n/2){ ok=k; break; }
}

cout<<(~ok?"YES":"NO")<<endl;
if(~ok){
if(ok==0)
for(int i=0;i<n/2;i++)
cout<<(i?" ":"")<<-1<<" "<<patt[ok][i];
else
for(int i=0;i<n/2;i++)
cout<<(i?" ":"")<<patt[ok][i]<<" "<<-1;
}

return 0;
}

まず、問題文の英語が難しい。
サンプルケースを図に描いてみてやっと理解した。
(↑で日本語に落とすのも苦労した。それでも多分読みにくいと思う。)
.
.
さてどうしよう。A問題なのに方針も浮かばない。
飛ばしてBへ進もう。(結局最後まで方針も立たなかった。)

[ 2010/09/19 追記 & 問題文の和訳修正 ]

問題文を読み間違えてたことが発覚。
棒は必ず1回だけ曲げるのね。曲げずに取り付けるパターンもありかと勘違いしてた。

そうと分かれば、棒をうまく取り付けた場合の配置は、
『釘1で1本の棒が折れ曲がっている』or『釘1で2本の棒がつながっている』
の2パターンしかない (他の棒の長さは自動的にすべて決まる) ので、両パターンについて実現可能かどうか調べるだけ。

ごちゃごちゃして、あまりきれいに書けなかった。

B.
vector<int> arr;

int UF_root(int i)
{
if(arr[i]==-1) return i;
return arr[i]=UF_root(arr[i]);
}

bool UF_find(int i,int j)
{
return UF_root(i)==UF_root(j);
}

void UF_union(int i,int j)
{
if(!UF_find(i,j))
arr[UF_root(j)]=UF_root(i);
}

int main()
{
int n; cin>>n;
arr=vector<int>(n,-1);

vector<int> perm(n);
for(int i=0;i<n;i++) cin>>perm[i],perm[i]--;

for(int i=0;i<n;i++){
int d; cin>>d;
if(0<=i-d) UF_union(i,i-d);
if(i+d<n) UF_union(i,i+d);
}

bool b=true;
for(int i=0;i<n;i++)
if(!UF_find(i,perm[i])) b=false;

cout<<(b?"YES":"NO")<<endl;

return 0;
}

問題を読んだ瞬間、Union-Findだと思った。
書いた。
submit. pretestにも1発で通った。
最後のSystemTestも通過して、何とかこの問題だけは Accepted。

方針は、Union-Findのデータ構造を使って、交換できる要素を1つの集合にまとめる。
その集合内では好きなように順序を入れ替えることができ、かつ他の集合内の要素とは交換できないから、
すべての i∈{1, 2, .., n} について、目標の順列 perm の i 番目の要素がセル i の含まれる集合に属していればいい。


解けたのは B だけで、
Ratingは16741603
Aを解けなかったのが悔やしい。わりとみんな解けてたのにな。

(他の問題も、解け次第追記予定)
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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