SRM 263 DIV1 Hard RobotRace - antaの競技プログラミング練習日記

問題

何人かとそれぞれのロボットとグリッドのマップがある。ロボットでレースをする。
マップは空白・壁・"token"・ロボットの開始地点マークからなる。
壁は'*'で表される。
各ロボットの開始位置は一意な、ロボットを表すアルファベット小文字で表される。
各tokenは一意な、トークンを表すアルファベット大文字で表される。
まず最初に予めロボットの動きを決めておかなければいけない。
このとき各人はスコアを最良にするように動きを決める。また、このとき他の人も最良に動くことを知っている。
動きは単位時間に"前方に進む","左に90°回転","右に90°回転"のどれか3つができる。
また、レースが始まる前にゲームを棄権することもできる。その場合は20ポイントのスコアだけを得られる。
その後ロボットは同時にスタートする。スタート時の向きは任意(90°単位でなければいけない)である。
ロボットは何体でも同じマスに同時に居ることが可能である。
ロボットは壁のある場所やマップの外に行った場合は失格する。
ロボットがtokenのある場所に行った場合、そのロボットはtokenをその取得しなければいけない。
同時に複数のロボットが同じtokenの位置に行こうとする場合はロボットを表すアルファベット小文字のアルファベット順で小さい方がtokenを得て、もう一方は失格する。
ロボットが取ったあとのtokenの場所には行けない。行ったら失格になる。
ロボットがtokenを取得した場合、ロボットとtokenの組み合わせごとに一定のスコアが与えられ、そのロボットはレースから外れる。
スコアはtokenValuesで": ..."のように表され、これはROBOTがx番目(0-origin)のTOKENを取った場合に(100-x)ポイントのスコアを得られることを意味する。ここに表示されていないtokenを取った場合はスコアは得られない。
各人がスコアを最良にするように動きを決めるとき、得られる各ロボットのスコアを、vectorで" "のように表してROBOTでソートして返せ

1*1 <= マップサイズ <= 50*50

解答

Editorialを参考にした。
まず下準備として、各ロボットと各トークンとの最小時間をBFSで求めておく。
問題は「各人が最良」という部分。これは最良安定マッチングでできる！
ロボットを左側に置き、tokenを右側に置く。数の足りない分は適当にダミーの頂点を追加しておく。
ロボット→tokenの優先順位は「そのtokenが有限時間で取れて、かつ得られるスコアの大きい方」(取れないトークンは優先度最小)。
token→ロボットの優先順位は「できるだけ先にこのトークンを取れるか」((最小時間,アルファベット)でソートする)。
これで左最良安定マッチングを求めれば、その一意の割当てがロボットとtokenの割り当てになる。ダミーの頂点に割り当てられた場合はtokenを取らない(棄権して20点)ということ。
なぜかを考えてみると、安定マッチングのブロッキングペアの制約が「『xのものよりyの方が欲しくて、かつyを取ってる人より先に取れる』ものが無い」というふうになる。
これは確かに求めたいものである。
また左最良というのは、あまりよくわかっていないが、単にスコア最大を求めたいからかな。
これで割り当てが求められる

しかし結構面白い問題だ。特にブロッキングペア制約の言い換えがうまくて面白い。
新しい問題ジャンル「安定マッチング」を見て、ある程度理解できてよかった。こういうことが楽しくてHard練習やってるんだよ！

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <sstream>
#include <cstring>
#include <cctype>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<string> vs;

vi stableMatching(const vector<vi>& v, const vector<vi>& u) {
	int n = v.size();
	vector<vi> p(n, vi(n+1, n));
	vi match(n, n), s(n, 0);
	rep(w, n) rep(i, n) p[w][u[w][i]] = i;
	rep(m0, n) for(int m = m0; m < n; ) {
		int w = v[m][s[m]++];
		if(p[w][m] < p[w][match[w]]) swap(m, match[w]);
	}
	return match;
}
struct RobotRace {
	vs b; int h, w;
	vector <string> getPrizes(vector <string> board, vector <string> tokenValues) {
		h = board.size(), w = board[0].size(); b = board;
		vector<pii> starts(26, mp(-1,-1)), tokenPoses(26, mp(-1,-1)); bool exists[26];
		mset(exists, 0);
		rep(i, h) rep(j, w) {
			if(islower(b[i][j])) starts[b[i][j]-'a'] = mp(i, j), exists[b[i][j]-'a'] = 1, b[i][j] = ' ';
			if(isupper(b[i][j])) tokenPoses[b[i][j]-'A'] = mp(i, j);
		}
		vi tokens[26];
		each(i, tokenValues) {
			string s = *i;
			char c = s[0];
			reu(j, 2, s.size()) tokens[c-'a'].pb(s[j]-'A');
		}
		static int d[26][55][55][4];
		mset(d, INF);
		//各初期位置から各位置までの最小時間をBFSで求める
		rep(i, 26) if(exists[i]) {
			vector<pair<pii,int> > q, next;
			rep(dir, 4) next.pb(mp(starts[i], dir));
			int t = 0;
			while(!next.empty()) {
				q.swap(next);
				while(!q.empty()) {
					pii p = q.back().first; int dd = q.back().second; q.pop_back();
					if(d[i][p.first][p.second][dd] <= t) continue;
					d[i][p.first][p.second][dd] = t;
					static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
					if(b[p.first][p.second] == ' ') rep(dir, 4) {
						int yy, xx, nd;
						if(dd == dir) yy = p.first + dy[dir], xx = p.second + dx[dir], nd = dd;
						else if((dd+1)%4 == dir || (dd+3)%4 == dir) yy = p.first, xx = p.second, nd = dir;
						else continue;
						if(yy<0||yy>=h||xx<0||xx>=w) continue;
						next.pb(mp(mp(yy, xx), nd));
					}
				}
				t ++;
			}
		}
		//dist[i][j] = ロボットiがtoken jに向かうときの最小時間
		static int dist[26][26];
		mset(dist, INF);
		rep(i, 26) if(exists[i]) {
			each(j, tokens[i]) {
				int x = INF;
				rep(dir, 4) x = min(x, d[i][tokenPoses[*j].first][tokenPoses[*j].second][dir]);
				dist[i][*j] = x;
			}
		}
		//各優先度を求める
		//存在しないロボット・tokenのところには優先度最小のダミー頂点を置く
		vector<vi> left(26), right(26);
		rep(i, 26) if(exists[i]) {
			rep(j, tokens[i].size()) if(dist[i][tokens[i][j]] != INF)
				left[i].pb(tokens[i][j]);
			set<int> s(all(left[i]));
			rep(j, 26) if(!s.count(j)) left[i].pb(j);
		}else rep(j, 26) left[i].pb(j);
		rep(i, 26) {
			vpii v;
			rep(j, 26) if(exists[j]) v.pb(mp(dist[j][i], j));
			sort(all(v));
			each(j, v) right[i].pb(j->second);
			rep(j, 26) if(!exists[j]) right[i].pb(j);
		}
		vi match_rev = stableMatching(left, right), match(26);
		rep(i, 26) match[match_rev[i]] = i;
		vs r;
		rep(i, 26) if(exists[i]){
			int p;
			aut(j, find(all(tokens[i]), match[i]));
			if(j == tokens[i].end()) p = 20;
			else if(dist[i][match[i]] == INF) p = 20;
			else p = 100 - (j - tokens[i].begin());
			stringstream ss;
			ss << char('a'+i) << " " << p;
			r.pb(ss.str());
		}
		return r;
	}
};

問題

解答

コメント

コード