AtCoder Beginner Contest 190 후기

ABC 190 간단 후기 올립니다~ (atcoder.jp/contests/abc190)

A - Very Very Primitive Game

간단한 구현 문제입니다. 먼저 시작하는 사람의 캔디가 더 많으면 먼저 시작하는 사람이 이기고, 그렇지 않으면 다른 사람이 이깁니다.

int main() {
	int a, b, c; cin >> a >> b >> c;
	if (c == 0) {
		if (a > b) cout << "Takahashi";
		else cout << "Aoki";
	}
	else {
		if (b > a) cout << "Aoki"; 
		else cout << "Takahashi";
	}
}

 

B - Magic 3

간단한 구현 문제입니다.  X < S and Y > D인 (X, Y)가 존재하면 Yes, 아니면 No를 출력하면 됩니다.

int main() {
	int n, s, d; cin >> n >> s >> d;
	int x, y;
	while (n--) {
		cin >> x >> y;
		if (x<s && y>d) {
			cout << "Yes"; return 0;
		}
	}
	cout << "No";
}

 

C - Bowls and Dishes

완전탐색 문제입니다. K명의 사람이 C or D를 선택하는 모든 경우(2^K)에 대하여 가장 많은 조건을 만족하는 경우를 출력하면 됩니다

typedef pair<int, int> p;
 
int N, M, K, ans, S[100];
p ab[100], cd[100];
 
void f(int idx) {
	if (idx == K) {
		int dish[104], i;
		for (i = 1; i <= N; i++) dish[i] = 0;
		for (i = 0; i < K; i++) {
			if (S[i] == 1) dish[cd[i].x] = 1;
			else dish[cd[i].y] = 1;
		}
		int sum = 0;
		for (i = 0; i < M; i++) {
			if (dish[ab[i].x] && dish[ab[i].y]) sum++;
		}
		ans = max(ans, sum);
		return;
	}
	S[idx] = 1; f(idx + 1);
	S[idx] = 2; f(idx + 1);
}
 
int main() {
	int i;
	cin >> N >> M;
	for (i = 0; i < M; i++) cin >> ab[i].x >> ab[i].y;
	cin >> K;
	for (i = 0; i < K; i++) cin >> cd[i].x >> cd[i].y;
	f(0);
	cout << ans;
}

 

D - Staircase Sequences

수학 문제입니다. 등차수열의 시작과 끝을 각각 a, b라고 할 경우 a + (a+1) + ... + b = N 인 (a, b) 쌍의 개수를 구하면 됩니다. 좌변은 (1+2+...+b) - (1+2+...+a-1) 이므로, b(b+1) - a(a-1)= 2N --> (b+a)(b-a+1)=2N이 됩니다.

2N을 xy꼴로 나타내서 x=b+a, y=b-a+1 or x=b-a+1, y=b+a가 성립하는지 확인하면 됩니다.

ll N;

inline int f(ll x, ll y) {
	if ((x + y - 1) % 2 == 0) return 1;
	return 0;
}
 
int main() {
	cin >> N;
	N *= 2;
	ll ans = 0;
	for (ll i = 1; i*i <= N; i++) {
		if (N%i) continue;
		ll j = N / i;
		if (f(i, j)) ans++;
		if (f(-i, -j)) ans++;
	}
	cout << ans;
}

 

E - Magical Ornament

Graph + bit DP 문제입니다. M개의 이웃한 쌍 (A,B)를 edge, N개의 gem이 node인 graph를 생각하자. K개의 C에 대하여 Ci에서 Cj의 shortest path를 구하자.(BFS 이용) 모든 (Ci, Cj) 쌍의 shortest path를 D[K][K]라고 하자. K개의 C를 node, D를 edge로 갖는 Graph에서 임의의 정점에서 다른 모든 노드를 방문하는 최소 비용 (salesman problem)을 구하면 된다.

int N, M, K, C[20], CC[100004], CI[100004], S[20];
vector<int> adj[100004];
int adj2[20][20];
const int INF = (int)1e9;
int dp[1 << 17][17];
 
int dfs(int state, int u) {
	int &ret = dp[state][u]; if (ret != -1) return ret;
	if (state == ((1 << K) - 1)) return ret = 0;
 
	ret = INF;
	for (int v = 0; v < K; v++) {
		if (state&(1 << v)) continue;
		if (adj2[u][v] == -1) continue;
		int a = dfs(state | (1 << v), v) + adj2[u][v];
		if (a < INF) ret = min(ret, a);
	}
	return ret;
}
 
int main() {
	int i, j;
	cin >> N >> M;
	for (i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	cin >> K;
	for (i = 0; i < K; i++) {
		cin >> C[i]; CC[C[i]] = 1; CI[C[i]] = i;
	}
 
	for (i = 1; i <= N; i++) {
		if (CC[i] == 0) continue;
		queue<int> q; q.push(i);
		vector<int> dist(N + 1, -1); dist[i] = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : adj[u]) {
				if (dist[v] != -1) continue;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
		for (j = 1; j <= N; j++) {
			if (CC[j] == 0 || i == j) continue;
			adj2[CI[i]][CI[j]] = adj2[CI[j]][CI[i]] = dist[j];
		}
	}
 
	int ans = INF;
	for (i = 0; i < (1 << K); i++) for (j = 0; j < K; j++) dp[i][j] = -1;
	for (i = 0; i < K; i++) {
		int ret = dfs(1 << i, i);
		if (ret < INF) ans = min(ans, ret + 1);
	}
	if (ans == INF) ans = -1;
	cout << ans;
}

 

F - Shift and Inversions

Segment Tree 문제입니다. i ~ i + N -1 구간의 inversion count를 구하면 됩니다. (0<= i <N) i=0일 경우는 segment tree를 이용하면 됩니다. (소스코드 rev_cnt) i=1 ~ N-1일 경우는 A[i]보다 작은 숫자와 큰 숫자는 O(1)에 찾을 수 있습니다. (소스크도 up, dn) 이유는 0 ~ N-1 숫자가 한 번씩 나오기 때문입니다.

struct sg {
	int st[1200004];
	void upd(int a, int b, int node, int node_st, int node_en) {
		if (a < node_st || node_en < a) return;
		if (node_st == node_en) {
			st[node] = b; return;
		}
		upd(a, b, node * 2, node_st, (node_st + node_en) / 2);
		upd(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
		st[node] = st[node * 2] + st[node * 2 + 1];
	}
	int qry(int a, int b, int node, int node_st, int node_en) {
		if (a > node_en || node_st > b) return 0;
		if (a <= node_st && node_en <= b) return st[node];
		return qry(a, b, node * 2, node_st, (node_st + node_en) / 2) +
			qry(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
	}
}S;
 
int main() {
	int i, n; cin >> n;
	vector<int> A(n + 1);
	ll rev_cnt = 0;
	for (i = 1; i <= n; i++) {
		cin >> A[i]; A[i]++;
		S.upd(A[i], 1, 1, 1, n);
		rev_cnt += (i - S.qry(1, A[i], 1, 1, n));
	}
	cout << rev_cnt << '\n';
	for (i = 1; i < n; i++) {
		int dn, up;
		dn = A[i] - 1; up = n - A[i];
		rev_cnt = rev_cnt - dn + up;
		cout << rev_cnt << '\n';
	}
}