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

kmjp's blog

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

AtCoder ARC #040 : A - 床塗り、B - 直線塗り

ARC#040に参加。
Dが解けなかったけどC早解きでいい順位になってしまった。
http://arc040.contest.atcoder.jp/tasks/arc040_a
http://arc040.contest.atcoder.jp/tasks/arc040_b

A - 床塗り

N*Nのグリッドの一部が赤か青で塗られている。
どちらが多いか答えよ。

愚直に数えるだけ。

int N;
string S[1010];
int R,B;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		FORR(r,S[i]) R+=(r=='R'),B+=(r=='B');
	}
	if(R>B) cout<<"TAKAHASHI"<<endl;
	if(R==B) cout<<"DRAW"<<endl;
	if(R<B) cout<<"AOKI"<<endl;
	
}

B - 直線塗り

左右に連続したN個のマスがあり、一部が塗られている。
プレイヤーは今一番左端のマスのいる。
1ターンごとに1マス右に移動するか、もしくは今の位置から右側Rマスまでのマスを塗ることができる。
全体を塗るまでに必要な最小ターン数を求めよ。

以下の何れかなら塗る方を選択する。

  • 今いるセルが塗られていない
  • 今の位置からRマスを塗ると、全体を塗りきることができる。

どちらでもない場合は右のマスに移動する。

int N,R;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>R>>S;
	int ret=0;
	x=0;
	while(1) {
		if(count(S.begin(),S.end(),'o')==N) break;
		ret++;
		if(S[x]=='.') {
			hoge:
			for(i=x;i<=x+R-1 && i<N;i++) S[i]='o';
		}
		else {
			int num=0;
			for(i=x+R;i<N;i++) num+=S[i]=='.';
			if(num==0) goto hoge;
			x++;
		}
	}
	cout<<ret<<endl;
}

まとめ

ここらへんはだいぶ簡単。
ABC並?

広告を非表示にする