読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

AtCoder ARC #024 : A - くつがくっつく、B - 赤と黒の木

ARC024に参加。ABCも凡ミスでWAを重ね、Dも結局解けきらなかったという微妙な回。
http://arc024.contest.atcoder.jp/tasks/arc024_1
http://arc024.contest.atcoder.jp/tasks/arc024_2

A - くつがくっつく

左足の靴のサイズ一覧と、右足の靴のサイズ一覧が与えらえる。
左右のサイズがそろった靴を最大何組作れるか。

同サイズの左足側がある分だけ、右足の数を数えればよい。

int L,R;
int LL[101],RR[101];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>L>>R;
	
	x=y=0;
	FOR(i,L) cin>>x,LL[x]++;
	FOR(i,R) {
		cin>>x;
		if(LL[x]>0) LL[x]--,y++;
	}
	cout << y << endl;
}

B - 赤と黒の木

円形にN個の木が並んでいる。
各木は赤か黒で塗られている。
1日ごとに、3つ連続同じ木が並んでいるとその真ん中の木の色を反転する。
最終的に木の色が変化しなくなるのは何日目か。

初期状態で全部の色が同じとき、毎日全部の木の色が反転するので永遠に続く。
それ以外の場合、x本同じ色の木が連続して並んでいたら1日あたり連続する数はx-2本になるので、(x+1)/2日後に反転が止まる。
よって、円形のうち同じ色の最長連続数yを求めて(y+1)/2を答えればよい。

int N;
int C[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	if(count(C,C+N,0)==N) return _P("-1\n");
	if(count(C,C+N,1)==N) return _P("-1\n");
	FOR(i,N) if(C[i]!=C[(i+N-1)%N]) break;
	vector<int> V;
	V.push_back(1);
	for(j=1;j<N;j++) {
		if(C[(i+j)%N]==C[(i+j-1)%N]) V.back()++;
		else V.push_back(1);
	}
	y=1;
	sort(V.begin(),V.end());
	
	cout << 1+(V.back()-1)/2 << endl;
	
}

まとめ

AもBも無駄WAしてもったいない…。

広告を非表示にする