kmjp's blog

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

Google Code Jam 2020 Qualification Round : A. Vestigium, B. Nesting Depth, C. Parenting Partnering Returns

今年も始まりました。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9

A. Vestigium

正方行列が与えられる。
正方行列の対角成分の和と、各行・列のうち同一の値を持つ要素が2つ以上あるものを数えよ。

これは問題の指示通り数えるだけ。

int N;
int A[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int NR=0,NC=0;
	int sum=0;
	cin>>N;
	FOR(y,N) {
		set<int> S;
		FOR(x,N) cin>>A[y][x], S.insert(A[y][x]);
		if(S.size()!=N) NR++;
		sum+=A[y][y];
	}
	FOR(x,N) {
		set<int> S;
		FOR(y,N) S.insert(A[y][x]);
		if(S.size()!=N) NC++;
	}
	
	
	
	_P("Case #%d: %d %d %d\n",_loop,sum,NR,NC);
}

B. Nesting Depth

数字で構築された文字列が与えられる。
隙間にカッコを入れ、各数字の位置が、その値の分のカッコで囲まれたようにせよ。

これは適宜数字の直前で、囲まれる数を調整するように開きカッコと閉じカッコを入れる。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	string S,R;
	cin>>S;
	int pre=0;
	FORR(c,S) {
		while(pre<c-'0') R+='(', pre++;
		while(pre>c-'0') R+=')', pre--;
		R+=c;
	}
	while(pre) R+=')', pre--;
	
	_P("Case #%d: %s\n",_loop, R.c_str());
}

C. Parenting Partnering Returns

いくつかの仕事があり、各時間帯が与えられる。
1つの仕事は1人でやる必要があり、1人は同時に1つの仕事しかできない。
2人でこの仕事を行うとき、全部の仕事を無事完了する割り当てを答えよ。

単にどん欲に空いてる人を割り当てていけばよい。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int N;
	vector<int> ev[1444];
	cin>>N;
	string S(N,'.');

	FOR(i,N) {
		cin>>x>>y;
		ev[x].push_back(N+i);
		ev[y].push_back(i);
	}
	
	int mask=0;
	int C[2]={-1,-1};
	FOR(i,1442) {
		sort(ALL(ev[i]));
		FORR(e,ev[i]) {
			if(e<N) {
				if(C[0]==e) C[0]=-1;
				else C[1]=-1;
			}
			else {
				x=e-N;
				if(C[0]==-1) {
					C[0]=x;
					S[x]='C';
				}
				else if(C[1]==-1) {
					C[1]=x;
					S[x]='J';
				}
				else {
					_P("Case #%d: IMPOSSIBLE\n",_loop);
					return;
				}
			}
		}
		ev[i].clear();
	}
	
	
	_P("Case #%d: %s\n",_loop,S.c_str());
}

まとめ

ここら辺までは指示通り行うだけかな。