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

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

10x10とグリッドが狭いので、(海でも島でも)任意の１マスを始点にして、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なみ？