Google Code Jam 2022 Qualification Round : A. Punched Cards, B. 3D Printing, C. d1000000

Eが解けず…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a4621b
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a4672b
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a46471

A. Punched Cards

カードサイズR*Cが指定されるので、角の欠けた文字列を描画せよ。

以下のコードでは、角の欠けない文字列を作り、最後に角を欠けさせている。

int R,C;
string S[30];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>R>>C;
	FOR(y,R+1) {
		S[y*2]="+";
		FOR(x,C) S[y*2]+="-+";
	}
	FOR(y,R) {
		S[y*2+1]="|";
		FOR(x,C) S[y*2+1]+=".|";
	}
	S[0][0]=S[0][1]=S[1][0]='.';
	
	cout<<"Case #"<<_loop<<":"<<endl;
	FOR(y,2*R+1) cout<<S[y]<<endl;
}

B. 3D Printing

3つのプリンタがあり、それぞれ4色のインクの残量が指定される。
4種類のインクの合計が10^6となるようにして文字を印刷したい。
同色のインクは各プリンタ同量使わなければならないとき、どのようなインク使用量にすれば条件を満たすか。

各色、3プリンタの最小値の分量だけ利用できるので、その範囲で合計10^6だけ使えばよい。

int C[3][4];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	FOR(y,3) FOR(x,4) cin>>C[y][x];
	int r=1000000;
	FOR(x,4) {
		C[0][x]=min({C[0][x],C[1][x],C[2][x],r});
		r-=C[0][x];
	}
	if(r) {
		cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
	}
	else {
		cout<<"Case #"<<_loop<<": "<<C[0][0]<<" "<<C[0][1]<<" "<<C[0][2]<<" "<<C[0][3]<<endl;
	}
}

C. d1000000

N個のダイスがあり、それぞれ何面かが与えられる。
全ダイスを振ったとき、L個連続した目がそれぞれ1個以上出る可能性があるような最大のLを求めよ。

目の数の多いL個のダイスを、目の数の小さい順に並べたとき、i番目のダイスがi以上の目を持てば、iの目を出す可能性があるので良い。
あとはLで二分探索しよう。
（なお、二分探索しなくても解けるっぽい）

int N;
ll S[101010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	sort(S,S+N);
	int ma=0;
	for(i=20;i>=0;i--) {
		int tmp=ma+(1<<i);
		if(tmp>N) continue;
		for(j=1;j<=tmp;j++) {
			if(S[N-1-(tmp-j)]<j) break;
		}
		if(j==tmp+1) ma=tmp;
	}
	
	cout<<"Case #"<<_loop<<": "<<ma<<endl;
}

まとめ

ここまではまだ前哨戦。