スポンサーサイト

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

Codeforces Beta Round #68

2011/04/16 0:00 ~ 2:00 (JST)
Codeforces Beta Round #68 の参加記録。

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

結果

点数より Accept した時間を書いたほうがいいことに気付いたので、これからそうする。

A. AC (00:03)
B. AC (00:26)
C. AC (01:54)
D. -
E. -
Hacks : -50 (0/1)
Standing : 100/1111
Rating : 17191862


問題

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

A. Room Leader
Codeforces のスコア計算式にしたがって、与えられる contestant の中でスコア最大の人を求めよ。

B. Train
controller と stowaway の 2 人が同じ電車に乗っている。
電車は n 輌編成。
controller は最初、m 輌目の車輌にいる。
stowaway は最初、k 輌目の車輌にいる。

各時刻において、電車は動いているか停まっているかのいずれかである。

controller の移動パターンは次のように定められる。
- 各時刻において、今、向いている方向に 1 車輌分移動する。
- 車輌の端まで来たら、向きを反転する。

stowaway の移動パターンは次のように定められる。
- 電車が動いているとき、今いる位置にとどまるか、隣接する車輌に移動する。
- 電車が停まっているとき、一旦電車の外に出て、任意の車輌に入る。

2 人が移動する順番は次のように定められる。
- 電車が動いているとき、stowaway が移動したあと、controller が移動する。
- 電車が停まっているとき、stowaway が外に出たあと、controller が移動し、最後に stowaway が電車に戻る。

2 人が最適な移動をしたとき、与えられた時間内に stowaway が controller につかまるかどうかを判定せよ。
stowaway と controller が同じ車輌にいるとき、stowaway は controller につかまるとする。

2 ≦ n ≦ 50
1 ≦ m, k ≦ n; m ≠ k
1 ≦ 時間の長さ ≦ 200

C. Chessboard Billiard
問題文の図を参照。
m × n の長方形でビリヤードをする。球は斜め 4 方向に移動することができ、壁で反射する。

どの 2 つの球も互いに衝突する位置にないような球の集合 S について、S の要素数は最大でいくつになるか?

2 ≦ m, n ≦ 106

D.
E.

解答

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

A.
int main(){
int n; cin>>n;
int score=-INF;
string leader;
rep(i,n){
string handle;
int plus,minus,a,b,c,d,e; cin>>handle>>plus>>minus>>a>>b>>c>>d>>e;
int tmp=100*plus-50*minus+a+b+c+d+e;
if(score<tmp){
score=tmp;
leader=handle;
}
}
cout<<leader<<endl;

return 0;
}

何も書くことがない。

B.
int main(){
int n,sto,con;
string to,dir,stat; cin>>n>>sto>>con>>to>>dir>>stat;
sto--,con--;
int len=stat.length();

rep(t,len){
if(stat[t]=='0'){
if(dir=="head"){
if(sto<con) sto=max(sto-1,0);
else sto=min(sto+1,n-1);
}
else{ // dir=="tail"
if(sto<con) sto=max(sto-1,0);
else sto=min(sto+1,n-1);
}
}
else{ // stat[t]=="1"
sto=-1;
}

if(dir=="head"){
con--;
if(con==0) dir="tail";
}
else{ // dir=="tail"
con++;
if(con==n-1) dir="head";
}

if(sto==con){
cout<<"Controller "<<t+1<<endl;
return 0;
}

if(stat[t]=='1'){
if((dir=="head" && con<n-1) || (dir=="tail" && con==0)) sto=n-1;
else sto=0;
}
}

cout<<"Stowaway"<<endl;

return 0;
}

controller の動き方は決まっているので、stowaway の動き方だけを考える。
stowaway ができるだけ長い時間つかまらないようにするには、
- 電車が動いているときは、controller から遠ざかる方向に移動する
- 電車が停まっているときは、controller が到達するのが一番遅い車輌 (先頭か末尾) に乗る
ようにすればいい。

C.
int main(){
int m,n; scanf("%d%d",&m,&n);
int cnt=0;
static bool checked[4][4][1000000];
rep(side,4)rep(t,side%2==0?n:m){
bool ok=true;
rep(dir,4)if(checked[dir][side][t]){ ok=false; break; }
if(!ok) continue;
cnt++;

const int tmp1=side,tmp2=t;
int dir=0;
while(!checked[dir][side][t]){
checked[dir][side][t]=true;
if(side==0){
if(dir==0) dir=3;
else if(dir==1) dir=2;
else if(dir==2){
if(t<m) side=1;
else side=2,t=t-m+1;
}
else{
if(n-t-1<m) side=3,t=n-t-1;
else side=2,t=t+m-1;
}
}
else if(side==1){
if(dir==0){
if(t<n) side=0;
else side=3,t=t-n+1;
}
else if(dir==1) dir=0;
else if(dir==2) dir=3;
else{
if(m-t-1<n) side=2,t=m-t-1;
else side=3,t=t+n-1;
}
}
else if(side==2){
if(dir==0){
if(n-t-1<m) side=3,t=m-(n-t-1)-1;
else side=0,t=t+m-1;
}
else if(dir==1){
if(t<m) side=1,t=m-t-1;
else side=0,t=t-m+1;
}
else if(dir==2) dir=1;
else dir=0;
}
else{
if(dir==0) dir=1;
else if(dir==1){
if(t<n) side=0,t=n-t-1;
else side=1,t=t-n+1;
}
else if(dir==2){
if(m-t-1<n) side=2,t=n-(m-t-1)-1;
else side=1,t=t+n-1;
}
else dir=2;
}
}
side=tmp1,t=tmp2;
}

printf("%d\n",cnt);

return 0;
}

長方形の縁以外の球を選ぶのは、動ける方向が 4 方向あって多くの軌道と干渉してしまうだけなのでよくない。
なので、最適解は縁にある球だけを使って構成できるはず。

それに気付けば、考えるべき位置は 4×106 箇所くらいなので、全部調べても間に合う。
Union-Find などを使ってもいいが、Greedy に選ぶ (順番に見ていってまだ使っていないものを選ぶ) だけで十分。

D.



E.



感想

ついにオレンジになった!!

A.
3 分は自己最速記録。
これ以上速くするためには、コンパイルが通ることを確認していてはダメかもしれない。

B.
問題文が正しく読み取れれば、それほど難しくないと思う。

C.
反射のパターンを全部書き下すのが大変だった。
デバッグも含め、この部分だけで 1 時間以上使った。
実は、とてもシンプルな O(1) 解法があった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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