Atcoder Beginner Contest 185 (ABC 185) 풀이

 

[문제 링크] 

 

atcoder.jp/contests/abc185

AtCoder Beginner Contest 185 - AtCoder

 

[풀이]

 

 

A. ABC Preparation

 

각 점수별로 문제 수가 나와있고, 하나의 문제 set을 만들기 위해서는 점수별로 하나씩 문제가 필요하다.

따라서 네 정수 중 최솟값을 출력하면 된다. 

 

#include<bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int a, b, c, d; cin >> a >> b >> c >> d;
	cout << min(min(a, b), min(c, d));
}

 

 

B. Smartphone Addiction

 

cafe에 있는 시간이 모두 겹치지 않고, 순서대로 주어지기 때문에 차례대로 다음 카페로 이동하는 시간은 빼주고, 카페이 있는 시간만큼은 배터리를 더해주면 된다. 

배터리의 최대 용량이 있는 점과, 집으로 돌아오는 것까지 고려해야 하는점을 주의하자.

 

#include<bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N, M, T; cin >> N >> M >> T;
	int last = 0;
	bool chk = true;
	int ori = N;
	for (int i = 1; i <= M; i++) {
		int a, b; cin >> a >> b;
		N -= (a - last);

		if (N <= 0) chk = false;
		N += b - a;

		N = min(N, ori);
		last = b;
	}
	N -= (T - last);
	if (N <= 0) chk = false;
	if (chk) cout << "Yes";
	else cout << "No";
}

 

 

C. Duodecim Ferra

 

주어진 막대를 12등분하는 문제이다. 

막대의 양 끝을 제외하고 간격 1만큼 모두 좌표가 주어져있다고 생각한다면, 좌표 중에서 11개를 고르는 경우의 수와 동일하다. 

따라서 조합(Combination)을 이용해서 Combi[L-1][11]을 구해주면 된다.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll combi[201][13];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	ll L;  cin >> L;
	combi[1][0] = combi[1][1] = 1;
	for (int i = 2; i <= L; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) combi[i][j] = 1;
			else combi[i][j] = combi[i - 1][j - 1] + combi[i - 1][j];
		}
	}
	cout << combi[L-1][11];
}

 

 

D. Stamp

 

다시 칠할 때에는 칠하는 구간이 겹쳐도 상관없기 때문에, 결국 연속된 white square 구간들의 길이가 stamp보다 크거나 같기만 하면 항상 해당 구간을 칠할 수 있다. 

따라서 파라메트릭 서치로 stamp의 최대 너비 k를 찾아준 후, 칠하는 횟수를 구해준다.

 

#include<bits/stdc++.h>
using namespace std;
int A[200010];
int N, M;
bool sol(int val) {
	for (int i = 1; i <= M+1; i++) {
		if (A[i] - A[i-1] >= 2 && A[i] - A[i - 1] - 1 < val) return false;
	}
	return true;
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) cin >> A[i];
	if (M == 0) {
		cout << 1;
		return 0;
	}
	sort(A + 1, A + 1 + M);
	A[M + 1] = N+1;
	int s = 1;
	int e = N;
	int ans = 0;
	while (s <= e) {
		int mid = (s + e) / 2;
		if (sol(mid)) {
			ans = max(ans, mid);
			s = mid + 1;
		}
		else e = mid - 1;
	}
	int res = 0;
	for (int i = 1; i <= M+1; i++) {
		res += (A[i] - A[i - 1] - 1) / ans + ((A[i] - A[i - 1] - 1) % ans == 0 ? 0 : 1);
	}
	
	cout << res;
}

 

 

E. Sequence Matching

 

DP문제이다. 

A'와 B'의 개수가 일치하도록 지우는 방식을, A와 B에서 계속해서 동시에 뽑는다고 생각하면 편리하다. 

그렇게 되면 자동으로 A'와 B'의 개수가 동일해진다. 

 

현재 배열 A에서의 index를 a라고 하고, B에서의 index를 b라고 하면, 세 경우가 나온다.

1. A[a]를 지운다. 

2. B[b]를 지운다.

3. A[a]와 B[b]를 뽑는다. 

 

1,2의 경우에는 지우는 비용 1이 필요하고, 3의 경우에는 A[a]와 B[b]가 다른 경우에만 비용이 1이 필요하게 된다.

 

#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;

int A[1001];
int B[1001];
int N, M;
int dp[1001][1001];
int sol(int a, int b) {
	if (a == N || b == M) {
		int ret = M - b + N - a;
		return ret;
	}
	int &ret = dp[a][b];
	if (ret != -1) return ret;
	ret = MAX;
	ret = min(ret, sol(a + 1, b) + 1);
	ret = min(ret, sol(a, b + 1) + 1);
	ret = min(ret, sol(a + 1, b + 1) + (A[a+1] != B[b+1] ? 1 : 0));
	return ret;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= M; i++) cin >> B[i];
	ini(dp, -1);
	cout << sol(0, 0);
}

 

 

F. Range Xor Query

 

세그트리의 전형적인 기본 유형 문제이다. XOR을 sum처럼 계산해줘도 무방하다.

 

#include<bits/stdc++.h>
using namespace std;

int A[300001];
int tr[1200001];
int init(int x, int s, int e) {
	if (s == e) return tr[x] = A[s];
	return tr[x] = init(x * 2, s, (s + e) / 2) ^ init(x * 2 + 1, (s + e) / 2 + 1, e);
}
int update(int x, int s, int e, int i, int val) {
	if (i < s || i > e) return tr[x];
	if (s == e) return tr[x] ^= val;
	else {
		return tr[x] = update(x * 2, s, (s + e) / 2, i, val) ^ update(x * 2 + 1, (s + e) / 2 + 1, e, i, val);
	}
}
int sum(int x, int s, int e, int l, int r) {
	if (s > r || e < l) return 0;
	if (s >= l && e <= r) return tr[x];
	else return sum(x * 2, s, (s + e) / 2, l, r) ^ sum(x * 2 + 1, (s + e) / 2 + 1, e, l, r);
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N, Q; cin >> N >> Q;
	for (int i = 1; i <= N; i++) cin >> A[i];
	init(1, 1, N);
	for (int i = 1; i <= Q; i++) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) {
			update(1, 1, N, x, y);
		}
		else {
			cout << sum(1, 1, N, x, y) << '\n';
		}
	}
}