kmjp's blog

競技プログラミング参加記です

Google Code Jam 2018 Qualification Round

無事全完でした。
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]);
	}
}

まとめ

ちょっと実行環境の不安定さが気になった。