Educational Codeforces Round 36 (Rated for Div. 2)

 A. Garden

  바닥에 물을 흘리지 않는 -> 약수인, 최대값을 찾으면 된다.

#include <cstdio>
int main() {
	int n, k,d,ans=1;
	scanf("%d%d", &n, &k);
	while (n--) {
		scanf("%d", &d);
		if (!(k%d)) ans = ans > d ? ans : d;
	}
	printf("%d", k / ans);
	return 0;
}

 B. Browser

  left, right가 존재하는 구간이 전체에 대해서 3가지 밖에 없다. 왼쪽에 몰린 경우, 오른쪽에 몰린 경우, 가운데에 있는 경우.

  이 세가지 경우를 고려하여 범위 및 Greedy 접근을 하여 해결한다.

#include <cstdio>
int abs_v(int a) { return a < 0 ? -a : a; }

int main() {
	int n, pos, l, r,ans=0;
	scanf("%d%d%d%d", &n, &pos, &l, &r);

	if (l != 1 && r != n) {
		ans += abs_v(r - l) + 1;
		if (abs_v(l - pos) <= abs_v(r - pos))
			ans += abs_v(l - pos) + 1;
		else ans += abs_v(r - pos) + 1;
	}
	else {
		if (l == 1 && r != n)
			ans += abs_v(r - pos) + 1;
		else if(l != 1 && r == n)
			ans += abs_v(l - pos) + 1;
	}

	printf("%d", ans);
	return 0;
}

 C. Permute Digits

  backtracking으로 구현하긴했는데, 그냥 막 구현하면 시간이 너무 오래걸린다. 따라서 "최대"값을 찾는 것에 의의를 두어 Greedy한 접근을 이용한다.

  또한 답이 항상 존재하기 때문에 backtracking이 실패할 일이 없다.

#include <iostream>
using namespace std;
using ll = long long;
ll a, b, ans,pow10[20];
int cnts[10], L;
bool back(int pos, ll d) {
	if (d*pow10[pos] > b) return 0;
	if (pos == 0) {
		if(b >= d) ans = ans > d ? ans : d;
		return 1;
	}
	for (int i = 9; i >= 0; i--) {
		if (cnts[i]) {
			cnts[i]--;
			if (back(pos - 1, d * 10 + i)) return 1;
			cnts[i]++;
		}
	}
	return 0;
}
int main() {
	cin >> a >> b;
	while (a) {
		cnts[a % 10]++;
		a /= 10;
		L++;
	}
	pow10[0] = 1;
	for (int i = 1; i <= L; i++) pow10[i] = pow10[i-1] * 10;
	back(L, 0);
	cout << ans;
	return 0;
}

 D. Almost Acyclic Graph

  위상정렬 개념을 이용하여 해결한다. in-degree가 1이상인 노드를 대상으로 in-degree을 하나 줄이면 그 노드로 들어가는 간선 중 하나를 지우는 것과 같다. 따라서 모든 노드에 대해 in-degree를 하나 감소하고, 사이클을 포함하는지 확인하고, in-degree를 하나 증가시키는 식으로 결과를 확인하면 된다.

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int cpyind[500], ind[500];
vector<vector<int>> adj;

bool GetCyclic(int V) {
	int i, ret = 0;
	queue<int> q;

	for (i = 0; i < V; i++) cpyind[i] = ind[i];
	for (i = 0; i < V; i++) if (!cpyind[i]) q.push(i);

	while (!q.empty()) {
		int u = q.front(); q.pop();
		ret++;
		for (int v : adj[u])
			if (--cpyind[v] == 0) q.push(v);
	}
	return ret == V;
}

int main() {
	int V, E, u, v, i, j, k, ans;
	scanf("%d%d", &V, &E);
	adj.resize(V);
	while (E--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		adj[u].push_back(v);
		ind[v]++;
	}
	if (GetCyclic(V)) {
		printf("YES"); return 0;
	}
	else {
		for (u = 0; u < V; u++) {
		    if(ind[u] == 0) continue;
			ind[u] -= 1;
			if (GetCyclic(V)) {
				printf("YES"); return 0;
			}
			ind[u] += 1;
		}
	}
	printf("NO");

	return 0;
}

 E. Physical Education Lessons

  segment tree with lazy propagation을 쓰면 MLE, 일반 구간(left, right) 자료구조를 쓰면 TLE가 뜬다 ㅡㅡ..

  따라서 정렬과 데이터 저장을 해줄 수 있는 set을 이용한다.

  set에는 non-work day 구간들이 들어 있으며, (right, left) 형식으로 저장한다. set 내 정렬 알고리즘이 있으므로 사용자 구조체를 쓴다면 operator< 를 오버라이딩 해줘야한다.

  들어오는 데이터 (l,r,k)에 대해 우선 set 내에 있는 겹치는 부분을 삭제해준다. 이것이 중요한데, 겹치는 부분을 삭제해주고, 나중에 k==1 이라면 set에 추가해준다.

  (4,1) (7,6)이 set에 들어있고, (4,7,1)이 들어왔다면, set에는 (3,1)이 남게되고 나중에 (7,4)를 저장하게된다. 결과적으로 (3,1)과 (7,4)가 set에 남게된다. 따라서 set에 남는 데이터들 간의 구간이 겹치는 일이 없어진다.

  데이터가 들어오고, set 내의 구간을 처리할 땐, work day를 늘려준다. set에 저장되는 것은 non-work day이기 때문에 구간이 줄어든다는 것은 곧 work day가 늘어나는 것을 의미한다. 또한 구간을 아예 벗어나면 while을 종료하고, 잘려 남겨진 구간에 대해서도 set에 추가해주는 구문이 필요하다.

+) lower_bound로 찾는 이유는 

1. set에 있는 모든 데이터 간의 겹치는(간섭되는) 부분이 없다.

2. 기본적으로 set은 정렬되어 있다.

를 이용한다.

두번째가 -1e9인 이유는 일단 l과 해당 위치의 r이 같다는 의미인데, 그 위치로 가기 위함이다. pair의 operator<를 생각해보자.

따라서 l에 대해서 set에 저장된 r의 값이 최초로 큰 위치를 찾게 된다. set에 저장된 r값이 l보다 작으면 아예 범위를 벗어나기 때문이다. 그림을 그려보면 쉽다.

=추천 문제===============================================================

https://www.acmicpc.net/problem/14595

======================================================================

#include <cstdio>
#include <set>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
int max_v(int a, int b) { return a > b ? a : b; }
int main() {
	int n,q,l,r,k,qi,cl,cr;
	set<pair<int, int>> s;
	scanf("%d%d", &n, &q);
	qi = n;
	while (q--) {
		scanf("%d%d%d", &l, &r, &k);
		auto cur = s.lower_bound(make_pair(l, -1e9));
		while (cur != s.end()) {
			cr = cur->first, cl = cur->second;
			if (min_v(r, cr) < max_v(l, cl)) break;
			qi += min_v(r, cr) - max_v(l, cl) + 1;
			s.erase(cur++);
			if (cl < l) s.insert(make_pair(l - 1, cl));
			if (r < cr) s.insert(make_pair(cr, r + 1));
		}
		if (k == 1) {
			s.insert(make_pair(r, l)); 
			qi -= r - l + 1; 
		}
		printf("%d\n", qi);
	}
	return 0;
}

 F. Imbalance Value of a Tree

 G. Coprime Arrays