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

kmjp's blog

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

AtCoder ARC #031 : A - 名前、B - 埋め立て

ARC

ARC#031に参加。
いつも通りD部分点の速解きで好順位。
http://arc031.contest.atcoder.jp/tasks/arc031_1
http://arc031.contest.atcoder.jp/tasks/arc031_2

A - 名前

文字列Sが回文か判定せよ。

S[i]==S[|S|-1-i]か判定するだけ。

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>s;
	FOR(i,s.size()) if(s[i]!=s[s.size()-1-i]) return _P("NO\n");
	_P("YES\n");
}

B - 埋め立て

10x10のグリッドが与えられる。
各セルは海か島かのいずれかである。
海のうち1マスを島にすることで、全部の島を隣接する島セルを辿って互いに移動可能になるか判定せよ。

10x10とグリッドが狭いので、(海でも島でも)任意の1マスを始点にして、Union-findなりBFSなりで連結判定をすればよい。

string S[10];

bool okok(int sy,int sx) {
	int vis[10][10];
	int y,x;
	
	ZERO(vis);
	FOR(y,10) FOR(x,10) if(S[y][x]=='x') vis[y][x]=1;
	vis[sy][sx]=1;
	
	queue<int> Q;
	Q.push(sy*10+sx);
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		
		int cy=k/10,cx=k%10,i;
		FOR(i,4) {
			int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
			int ty=cy+dy[i],tx=cx+dx[i];
			if(tx<0 || tx>=10 || ty<0 || ty>=10) continue;
			if(vis[ty][tx]) continue;
			vis[ty][tx]=1;
			Q.push(ty*10+tx);
		}
	}
	
	FOR(y,10) FOR(x,10) if(vis[y][x]==0) return false;
	return true;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(y,10) cin>>S[y];
	
	FOR(y,10) FOR(x,10) if(okok(x,y)) return _P("YES\n");
	_P("NO\n");
}

まとめ

ARCにしてはA,B共に簡単。ABCなみ?

広告を非表示にする