スポンサーサイト

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

Codeforces Beta Round #60

2011/03/06 1:00~3:00 (JST)
Codeforces Beta Round #60 の参加記録

Rating の色分けが変更されてからはじめての Codeforces.

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

結果

A. Hacked,WA
B. AC(810)
C. WA
D. -
E. -
Hacks : +200 (2 hacked)
Standing : 231/1265
Rating : 17001715


問題

問題セットの原文はここを参照。
今回の問題セットはハリー・ポッターシリーズ。

A. Harry Potter and Three Spells
a グラムの砂を b グラムの鉛に変える魔法と
c グラムの鉛を d グラムの金に変える魔法と
e グラムの金を f グラムの砂に変える魔法がある。
このとき、有限の砂から無限の金を作ることができるかどうかを判定せよ。
( a, b, .., f は 0 以上 1000 以下の整数 )

B. Harry Potter and the History of Magic
n (≦ 1000) 個の年号が与えられる。
各年号の数字を高々 1 桁だけ変えることで、年号を年代順 (年号の非減少順) に並べよ。
また、各年号は 1000 以上 2011 以下でないといけない。
答えが複数ある場合はどれを答えてもいい。
そのような変更ができない場合はそれを報告せよ。

C. Harry Potter and the Golden Snitch
スニッチの軌道が n (≦ 10000) 頂点の折れ線として与えられる。
スニッチの初期位置、スニッチの速度、ハリーの初期位置、ハリーの速度が与えられる。
( ハリーの速度 ≧ スニッチの速度 が保証されている。)
ハリーの座標とスニッチの座標が一致したとき、ハリーはスニッチを捕まえることができる。

ハリーがスニッチを捕まえることのできる最短時間とその位置を求めよ。
( 出力は 10-6 以下の誤差を含んでいてもいい。)
折れ線の終端までに捕まえられない場合はそれを報告せよ。

D.
E.
あとで読む。

解答

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

A. (時間外)
int main(){
int a,b,c,d,e,f; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
double m1,m2,m3;
if(a>0) m1=1.*b/a; else m1=b*1e30;
if(c>0) m2=m1*d/c; else m2=d*1e30;
if(e>0) m3=m2*f/e; else m3=f*1e30;

puts((m1>1e29 && m2>0) || m2>1e29 || (m1>0 && m2>0 && m3>1) ? "Ron" : "Hermione" );

return 0;
}

1 回 Hack されて再提出したにもかかわらず、WA だった。

どのパラメータが 0 になるかという場合分けを考えるとかなり大変。
次のように考えれば、ちょっとは楽かもしれない。

無限の金を得ることができたとすれば、
・ 砂→鉛→金 の 1 過程で無限の金を作ることができる
・ 砂→鉛→金→砂 の 1 サイクルで金の量を増やすことができる
のどちらかしかない。

前者は
・ 無限の鉛を作ることができて、かつ、(少なくとも微量の) 金を作ることができる
・ 無限の金を作ることができる
のどちらか。

後者は
・ 1 サイクルしたときの砂の量が元の砂の量より多い、かつ、砂から (少なくとも微量の) 金を作ることができる
しかない。

B.
int main(){
int n,y[1000]; scanf("%d",&n);
bool b=true;
rep(i,n){
scanf("%d",y+i);
int yopt=9999;
rep(j,4)for(int d=(j?0:1);d<=9;d++){
char s[8]; sprintf(s,"%d",y[i]);
s[j]=d+'0';
int yy; sscanf(s,"%d",&yy);
if(1000<=yy && yy<=2011 && (i==0 || y[i-1]<=yy)) yopt=min(yopt,yy);
}
y[i]=yopt;
if(y[i]<1000 || 2011<y[i] || (i>0 && y[i]<y[i-1])) b=false;
}

if(b) rep(i,n) printf("%d\n",y[i]);
else puts("No solution");

return 0;
}

各年号について、できるだけ小さい年号におきかえていけばいい。
つまり、Greedy Algorithm.

(解がある場合に) Greedy で正しい解が得られることの証明も、そんなに難しくないと思う。
Greedy 解が許容解であることは明らか。
各年号において、Greedy 解のほうが最適解より早い (or 同じ) であることは、年号の選び方から明らか。
帰納的に、年代のすべての時点において、Greedy のほうがいい解 (or 同じ解) を与えているはず。

C. (時間外)
const double EPS=1e-11;

inline double sq(double a){ return a*a; }
inline double dis(double a,double b,double c){ return sqrt(sq(a)+sq(b)+sq(c)); }

int n,x[10001],y[10001],z[10001],v_po,v_sn,x_po,y_po,z_po;
double t_sn[10001];

double isCatchable(double t_sn,double x_sn,double y_sn,double z_sn){
return dis(x_sn-x_po,y_sn-y_po,z_sn-z_po)/v_po<t_sn+EPS;
}

double calc(int k,double &x_ans,double &y_ans,double &z_ans){
double sl=0,sr=t_sn[k]-t_sn[k-1];
double ux=x[k]-x[k-1],uy=y[k]-y[k-1],uz=z[k]-z[k-1];
double uabs=dis(ux,uy,uz); ux/=uabs; uy/=uabs; uz/=uabs;
double vx=v_sn*ux,vy=v_sn*uy,vz=v_sn*uz;

double sm,xx,yy,zz;
rep(i,100){
sm=(sl+sr)/2;
xx=x[k-1]+vx*sm;
yy=y[k-1]+vy*sm;
zz=z[k-1]+vz*sm;
if(isCatchable(t_sn[k-1]+sm,xx,yy,zz)) sr=sm;
else sl=sm;
}

x_ans=xx;
y_ans=yy;
z_ans=zz;
return t_sn[k-1]+sm;
}

int main(){
scanf("%d",&n); n++;
rep(i,n) scanf("%d%d%d",x+i,y+i,z+i);
scanf("%d%d%d%d%d",&v_po,&v_sn,&x_po,&y_po,&z_po);

bool ok=false;
double l_sn=0;
double t_ans,x_ans,y_ans,z_ans;
for(int i=1;i<n;i++){
l_sn+=dis(x[i]-x[i-1],y[i]-y[i-1],z[i]-z[i-1]);
t_sn[i]=l_sn/v_sn;
double l_po=dis(x[i]-x_po,y[i]-y_po,z[i]-z_po);
double t_po=l_po/v_po;

if(t_po<t_sn[i]+1e-9){
t_ans=calc(i,x_ans,y_ans,z_ans);
ok=true;
break;
}
}

if(ok) printf("YES\n%.9f\n%.9f %.9f %.9f\n",t_ans,x_ans,y_ans,z_ans);
else puts("NO");

return 0;
}

提出したプログラムはシステムテストで落ちた。
誤差死だった。
昨日書いた記事がフラグだとは思わなかった。

空間幾何の問題。
ハリーの最適ルートはもちろん直線なので、スニッチの位置が与えられたときにハリーがスニッチを捕れるかどうかの判定は難しくない。
( ハリーがその位置に着く時刻 ≦ スニッチがその位置に着く時刻 であればいい )

なので、最適解が折れ線の何番目の線分にあるかを線形探索していって、線分が特定できたところで、線分の両端から範囲を絞っていく二分探索に切り替えればいい。

二分探索の精度を 10-11 にすれば AC だった。( 10-10 では WA )
なぜ -11 でいいのかはよくわからない。

実はこの問題は、二分探索しなくても、線分が特定できた時点で解析的に解を求められる。
そっちのほうが誤差が少ないので良い解法なんだと思う。

D.



E.


スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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