Hatena::Grouptopcoder

zerokugi's contest memo

2014-08-13SRM629 Div1 Easy Med

oo- +0/-0 368.15pts. (39th) 19402043

Easy - RectangleCovering

問題

与えられた板を使って穴を塞ぐことはできるか、できるなら最小何枚必要か

ただし板の4隅は穴の外(境界を除く)にないといけない

解法

全て縦に敷き詰めていくか横に敷き詰めていくかの2通りだけ考えてやればよい

int check(int holeH, int holeW, const vector <int> &H, const vector <int> &W){
	int n = H.size();
	vector<int> can;
	REP(i, n){
		int res = 0;
		if(H[i] > holeW) res = W[i];
		if(W[i] > holeW) res = max(res, H[i]);
		can.push_back(res);
	}
	sort(can.rbegin(), can.rend());		// でかいのから貪欲に取っていく
	int sum = 0;
	REP(i, can.size()){
		sum += can[i];
		if(sum >= holeH) return i+1;
	}
	return INF;
}
int minimumNumber(int holeH, int holeW, vector <int> H, vector <int> W) {
	int ans = min(check(holeH, holeW, H, W), check(holeW, holeH, H, W));
	return ans == INF ? -1 : ans;
}

これみたいに関数化してwh入れ替えて2回呼び出す方法、初歩的だけどわりと有用だと思う

(チャレンジフェイズで青コーダーの人のコードを見ると2回書いてたりしてる人が多かった)

Medium - CandyCollection

問題

飴を売る店がN個ある

飴にはN種類の味があり,0 ~ N-1 まで番号付けされている

それぞれの店は2種類の飴(t1[i] と t2[i])がそれぞれ n1[i] 個と n2[i] 個ずつ売っている

飴の形は店によって違うが,同じ店で売られている2種類の味の飴の形は同じである

なお,全ての味について同じ味の飴(形は違う)を売っている店がかならず2店舗ある

N 種類の味の飴を全て揃えるためには最低何個の飴を買う必要があるか

解法

まず一つの店に対して行える操作は

  • min(n1, n2)+1 個買う(多い方だけ手に入る)
  • max(n1, n2)+1 個買う(両方手に入る)
  • 買わない

の3つだけ考えればよい

N種類の味を頂点として、同じ店で売っている飴同士に辺を張ったグラフを考えると,全ての頂点が次数2になるのでサイクルの集合になることがわかる。

このグラフ上で、全ての頂点(飴)に対して

  • 隣り合う2頂点をまとめて買う
  • 1頂点のみ買う

の二通り試してやるとよい

適当に始点を決める→右回り左回りかで2回dfs(メモ化再帰)する とすると楽

struct Edge{
	int to, x, y, rev;
	Edge(int t=0,int xx=0,int yy=0, int r=0){
		to=t;x=xx;y=yy;rev=r;
	}
};
vector<Edge> g[1001];

int dfs(int r, int rev, int goal, vi &memo){		// rev は直前に辿ってきた辺の番号0 or 1
	if(memo[r] != -1) return memo[r];

	Edge &next = g[r][!rev];			// 次に進む辺
	int res = min(g[r][0].y+1, g[r][1].y+1);	// ノード r のみを取るコスト
	if(next.to == goal) return memo[r] = res;	// 1個先が始点
	res += dfs(next.to, next.rev, goal, memo);
	
	Edge next2 = g[next.to][!next.rev];		// 次の次に進む辺
	int res2 = max(next.x, next.y) + 1;		// ノード r と次をまとめて取るコスト
	if(next2.to == goal)				// 2個先が始点
		return memo[r] = min(res, res2);
	return memo[r] = min(res, res2 + dfs(next2.to, next2.rev, goal, memo));
}

int solve(vector <int> t1, vector <int> n1, vector <int> t2, vector <int> n2) {
	int n = t1.size();
	REP(i, n){
		int r1 = g[t2[i]].size();
		int r2 = g[t1[i]].size();
		g[t1[i]].emplace_back(t2[i], n1[i], n2[i], r1);
		g[t2[i]].emplace_back(t1[i], n2[i], n1[i], r2);
	}
	vector<int> memo1(n, -1), memo2(n, -1);
	int ans = 0;
	REP(i, n)
		if(memo1[i] == -1)
			ans += min(dfs(i, 0, i, memo1), dfs(i, 1, i, memo2));
	return ans;
}

こういう問題は実装ゲーというより設計ゲーと言った方がよい気がする