無事全完でした。
https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard
Saving The Universe Again
初期攻撃力を1としたとき、以下のコマンドで構成されたシーケンスが与えられる。
- 攻撃力を倍にする
- 今の攻撃力の分ダメージを与える
2つの隣接するコマンド順を逆にできる場合、ダメージをD以下にするには何回逆にすればよいか。
「倍→ダメージ」の並びのうち一番後ろにあるものを反転するとダメージ量を最も小さくできるので、それを繰り返す。
ll D; string P; ll damage(string S) { ll cur=1,tot=0; FORR(c,S) { if(c=='C') cur*=2; else tot+=cur; } return tot; } void solve(int TC) { int i,j,k,l,r,x,y; string s; cin>>D>>P; int num=0; while(1) { if(damage(P)<=D) return _P("Case #%d: %d\n",TC,num); num++; for(i=P.size()-1;i>=0;i--) { if(P[i]=='C'&&P[i+1]=='S') { swap(P[i],P[i+1]); break; } } if(i==-1) break; } _P("Case #%d: IMPOSSIBLE\n",TC); }
Trouble Sort
整数列Aに対し、トラブルソートとはA[i]>A[i+2]であるiがある限り両者のswapを繰り返すものである。
Aが与えられたとき、このソートで正しくソートできるか判定せよ。
奇数位置と偶数位置の要素を分けて個別にソートしてまた連結し、ソートされているか判定すればよい。
int N; void solve(int TC) { int i,j,k,l,r,x,y; string s; cin>>N; vector<int> A[2],B; FOR(i,N) { cin>>x; A[i%2].push_back(x); } sort(ALL(A[0])); sort(ALL(A[1])); FOR(i,N) B.push_back(A[i%2][i/2]); FOR(i,N-1) { if(B[i]>B[i+1]) return _P("Case #%d: %d\n",TC, i); } _P("Case #%d: OK\n",TC); }
Go, Gopher!
グリッド状1個の場所を指定すると、そこもしくは周辺8マスを含む9マスのいずれかが当確率で選択され、塗りつぶされる。
1000回以下の指定で、以下を満たすようにセルを塗れるか。
- 矩形領域の周辺部が塗りつぶされている
- その矩形中A個以上のセルが塗られている。
LargeのA=200の例を考える。
面倒なので(1,1)-(10,20)を塗りつぶすことを考えよう。
(2,2)-(9,19)を指定して周囲9マスが埋まるまで塗りつぶしを指定すればよい。ただこれだと確率的に1000回で終わるかわからない。
(x,y)を指定する際、(x-1,y-1)以外のセルは(x,y+1)や(x+1,y)を指定して塗られる可能性があるので、(x-1,y-1)だけ埋まったらさっさと次に行くようにするとよい。
int A; int H,W; int did[25][25]; void dig(int y,int x) { int i,j; while(1) { int num=0; if(y<H-1 && x<W-1) { if(did[y-1][x-1]==0) return; } FOR(i,3) FOR(j,3) num+=did[y-1+i][x-1+j]; if(num==0) break; cout<<x<<" "<<y<<endl; cin>>i>>j; if(i==0&&j==0) ZERO(did); did[j][i]=0; } } void solve(int TC) { int i,j,k,l,r,x,y; string s; cin>>A; if(A==20) H=4,W=5; if(A==200) H=10,W=20; ZERO(did); for(x=1;x<=W;x++) for(y=1;y<=H;y++) did[y][x]=1; for(y=2;y<=H-1;y++) for(x=2;x<=W-1;x++) dig(y,x); }
Cubic UFO
3次元空間上で原点を中心として(±0.5,±0.5,±0.5)を頂点とする立方体がある。
この立方体を回転させ、XZ平面に投影したときの面積がAとなるようにしたい。回転行列を答えよ。
- 1≦A≦√2の場合
- 立方体をZ軸にそって最大45度まで傾けると面積が増える。真面目に方程式を解いてもいいかもしれないが、二分探索で十分。
- √2≦A≦√3の場合
- 上記のとおり45度傾けた状態で、今度はX軸にそって最大Θ(tanΘ=1/√2)まで傾けると面積が増える。あとは同様に二分探索。
int T,testcase; double A; vector<double> rotz(vector<double> V,double d) { double s=sin(d),c=cos(d); vector<double> R(3); R[0]=c*V[0]-s*V[1]; R[1]=s*V[0]+c*V[1]; R[2]=V[2]; return R; } vector<double> rotx(vector<double> V,double d) { double s=sin(d),c=cos(d); vector<double> R(3); R[0]=V[0]; R[1]=c*V[1]-s*V[2]; R[2]=s*V[1]+c*V[2]; return R; } double sqarea(vector<double> A,vector<double> B,vector<double> C) { int i; FOR(i,3) B[i]-=A[i], C[i]-=A[i]; B[1]=C[1]=0; double X=B[1]*C[2]-B[2]*C[1]; double Y=B[2]*C[0]-B[0]*C[2]; double Z=B[0]*C[1]-B[1]*C[0]; return sqrt(X*X+Y*Y+Z*Z); } double area(double rz,double rx) { vector<vector<double>> D={ {0.5,0.5,0.5}, {-0.5,0.5,0.5}, {-0.5,-0.5,0.5}, {0.5,-0.5,0.5}, {0.5,0.5,-0.5}, {-0.5,0.5,-0.5}, {-0.5,-0.5,-0.5}, {0.5,-0.5,-0.5} }; FORR(d,D) d=rotx(rotz(d,rz),rx); vector<vector<int>> F={ {0,1,2,3}, {4,5,6,7}, {0,1,5,4}, {1,2,6,5}, {2,3,7,6}, {3,0,4,7}, }; double A=0; FORR(f,F) A+=sqarea(D[f[0]],D[f[1]],D[f[3]]); return A/2; } void solve(int TC) { int i,j,k,l,r,x,y; string s; double pi=atan(1)*4; cin>>A; double rx=0,rz=0; if(A<=sqrt(2)) { double L=0,R=pi/4; FOR(i,200) { double M=(L+R)/2; if(area(M,0)<=A) L=M; else R=M; } rz=L; } else { rz=pi/4; double L=0,R=atan2(1,sqrt(2)); FOR(i,200) { double M=(L+R)/2; if(area(rz,M)<=A) L=M; else R=M; } rx=L; } vector<vector<double>> D={ {0.5,0,0}, {0,0.5,0}, {0,0,0.5}, }; _P("Case #%d:\n", TC); FORR(d,D) { d=rotx(rotz(d,rz),rx); _P("%.10lf %.10lf %.10lf\n",d[0],d[1],d[2]); } }
まとめ
ちょっと実行環境の不安定さが気になった。