kmjp's blog

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

Indeedなう(本選A) : A - Table Tennis、B - Office Ninja

本番不参加。F以外は何とか自力で解けました。
http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_a
http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_b

A - Table Tennis

N人(偶数)の選手がおり、個人の強さはA[i]である。
選手を2人ずつ組にし、N/2組のダブルスペアを作る。その際、ダブルスの強さは2人の強さの和である。
ダブルスペアの強さの最大値と最小値の差を最小化せよ。

選手をソートし、強い選手と弱い選手を順にペアにしていけばよい。

int N;
int A[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N/2) A[i]+=A[N-1-i];
	sort(A,A+N/2);
	cout << A[N/2-1]-A[0]<<endl;
}

B - Office Ninja

Hex Mapと各マスに侵入するコストが与えられる。
始点から終点への移動の最小コストを答えよ。

Hex Mapなので隣接マスの処理が少々面倒だが、それを除けば単なるDijkstra。

int H,W;
string S[1010];
int dist[200][200];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int sy,sx,gy,gx;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='s') S[y][x]='0', sy=y,sx=x;
		FOR(x,W) if(S[y][x]=='t') S[y][x]='0', gy=y,gx=x;
		FOR(x,W) dist[y][x]=10000000;
	}
	dist[sy][sx]=0;
	priority_queue<pair<int,int> > Q;
	Q.push(make_pair(0, sy*1000+sx));
	while(Q.size()) {
		auto r=Q.top();
		Q.pop();
		int cy=r.second/1000, cx=r.second%1000;
		if(-r.first != dist[cy][cx]) continue;
		
		FOR(i,6) {
			int dx[6]={-1,0,-1,1,-1,0}, dy[6]={-1,-1,0,0,1,1};
			int ty=cy+dy[i],tx=cx+dx[i];
			if(dy[i]) tx += cy%2;
			if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
			int co=dist[cy][cx] + S[ty][tx]-'0';
			if(co < dist[ty][tx]) {
				dist[ty][tx] = co;
				Q.push(make_pair(-co, ty*1000+tx));
			}
		}
	}
	cout << dist[gy][gx] << endl;
}

まとめ

Bのインデックスの張り方が想定と違っていて、WAを連発してしまった。