고급반 8주차 풀이 - 수고했어요 (4 / 17)

1. [2183] 테니스 시합 (Bronze II)

입력은 하나의 완전한 시합입니다.

그러니 입력의 끝 = 시합의 끝이 되고, 시합의 마지막 경기를 이긴 사람이 최종 승자가 될 때 시합이 끝나기 때문에

결국 마지막 경기를 이긴 사람 = 입력의 마지막 글자가 답이 됩니다.

void Main(){
	int n; string s; cin >> n >> s; int sl = s.size();
	cout << s[sl-1];
}

2. [14574] 헤븐스 키친 (Platinum V)

두 참가자 \( v, w \)가 대결할 때의 시청률 \( x \)를 다 가중치 간선으로 만들어버리면

문제는 Maximum Spanning Tree를 찾고, 이를 이루는 간선들을 찾는 문제가 됩니다.

앞부분은 Well-known이고, 뒷부분은 완성된 트리에서 DFS를 돌리면서 "이전 정점, 현재 정점"의 순서로 출력해주면 됩니다.

pl2 arr[1020];
vector<int> adj[1020];

int par[1020];
int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); }
void uni(int a, int b){ par[fnd(a)] = fnd(b); }

void dfs(int now, int pre){
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
	if (pre != -1){ cout << pre << ' ' << now << endl; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	for (int i = 1; i <= n; i++){ cin >> arr[i].sc >> arr[i].fr; }
	priority_queue<pl3> pq;
	for (int i = 1; i <= n; i++){
		for (int j = i+1; j <= n; j++){
			pq.push({ (arr[i].fr+arr[j].fr)/abs(arr[i].sc-arr[j].sc), {i, j} });
		}
	}
	ll ans = 0;
	while (!pq.empty()){
		ll x = pq.top().fr;
		int v = pq.top().sc.fr, w = pq.top().sc.sc;
		pq.pop();
		if (fnd(v) == fnd(w)){ continue; } uni(v, w);
		ans += x;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	cout << ans << endl;
	dfs(1, -1);
}

3. [21398] 동생에게 져주기 (Platinum V)

\( DP_{l, r, x, t} := \) \( t \)의 차례일 때, \( S \)에서 \( S[l:r] \)로 오면서 \( x \)점 차를 만들 수 있는가? 를 정의해봅시다.

이제 이게 어떻게 전파되는지 관찰해봅시다.

• \( t = \text{Albert} \): 문제에서 나온 전략대로 시행합니다. 그리고 이 전략은 좌측의 카드가 2점을 준다면 좌측의 카드를, 아니면 우측의 카드를 가져간다와 동일합니다.
• \( t = \text{Alice} \): 왼쪽 카드를 가져가는 경우와 오른쪽 카드를 가져가는 경우 둘 다 시행해보면 됩니다.

실제 DP 구현에는 \( l, r \)로 \( t \)를 유추할 수 있으니 \( DP_{l, r, x} \)로 구현해주면 됩니다.

inline bool alb(char ch){ return ch=='A' || ch=='L' || ch=='B' || ch=='E' || ch=='R' || ch=='T'; }
inline bool alc(char ch){ return ch=='A' || ch=='L' || ch=='I' || ch=='C' || ch=='E'; }

const int INF = 1e9;

const int ZERO = 155; int ans = 1e9;
string s; bool dp[160][160][460];
void dpf(int st, int ed, int scr, int trn){
	//cout << "DP " << st << ' ' << ed << ' ' << "   " << scr << ' ' << trn << endl << flush;
	if (st > ed){
		if (scr > 0){ ans = min(ans, scr); }
		return;
	}
	if (dp[st][ed][scr+ZERO]){ return; } dp[st][ed][scr+ZERO] = 1;
	if (trn == 0){
		int l = 2*alb(s[st]), r = 2*alb(s[ed]);
		if (l){ return dpf(st+1, ed, scr+l, 1); }
		return dpf(st, ed-1, scr+r, 1);
	}
	else{
		dpf(st+1, ed, scr-alc(s[st]), 0);
		dpf(st, ed-1, scr-alc(s[ed]), 0);
	}
}

void Main(){
	int t; cin >> t; while (t--){
		memset(dp, 0, sizeof(dp));
		cin >> s; int sl = s.size();
		ans = 1e9; dpf(0, sl-1, 0, 0);
		cout << (ans==INF ? -1 : ans) << endl;
	}
}

4. [13344] Chess Tournament (Platinum V)

둘의 실력이 같다면, 그냥 둘을 같은 사람 취급해도 됩니다. 이는 DSU로 처리할 수 있습니다.

그럼 남은 건 실력차가 있는 경우밖에 없는데, 이를 모두 방향성 간선으로 만들어준 뒤 DAG인지 판별해주면 됩니다.

vector<pi2> edg;

int par[50020];
int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); }
void uni(int a, int b){ par[fnd(a)] = fnd(b); }

vector<int> adj[50020];
int pac[50020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	while (m--){
		int v, w; string op; cin >> v >> op >> w; v += 1; w += 1;
		if (op == "="){ uni(v, w); }
		if (op == ">"){ edg.push_back({v, w}); }
	}
	int cnt = 0; for (int i = 1; i <= n; i++){ cnt += fnd(i) == i; }
	//cout << "C " << cnt << endl;
	for (pi2 p : edg){
		int v = p.fr, w = p.sc;
		adj[fnd(v)].push_back(fnd(w)); pac[fnd(w)] += 1;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++){
		if (fnd(i) != i){ continue; }
		if (pac[i] == 0){ q.push(i); }
	}
	while (cnt--){
		if (q.empty()){ cout << "inconsistent"; return; }
		int now = q.front(); q.pop();
		//cout << "Q " << cnt+1 << ' ' << now << endl;
		for (int nxt : adj[now]){
			pac[nxt] -= 1; if (pac[nxt] == 0){ q.push(nxt); }
		}
	}
	cout << "consistent";
}

Not Solved

5. [15634] Glen (Platinum V)

6. [3648] 아이돌 (Platinum IV)

7. [16440] 제이크와 케이크 (Platinum IV)

8. [24489] Farm Updates (Platinum II)

9. [14164] 삼각형 영역 (Platinum I)

10. [17399] 트리의 외심 (Platinum I)

11. [23836] 어떤 우유의 배달목록 (Hard) (Diamond V)

12. [20297] Confuzzle (Diamond V)

13. [12702] Endless Knight (Large) (Diamond V)

14. [12918] 정리정돈 (Diamond IV)

15. [5573] 산책 (Platinum IV)

16. [13952] Hanger Hurdles (Diamond IV)

17. [8481] Generator (Diamond III)