Atcoder Beginner Contest 281

 

https://atcoder.jp/contests/abc281

AtCoder Beginner Contest 281 - AtCoder

 

A. Count Down

 

 

요약

 

 

N보다 작거나 같은 음수가 아닌 정수를 내림차순으로 출력한다.

---

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

int N;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = N; i >= 0; i--) cout << i << '\n';
	return 0;
}

 

 

 

B. Sandwich Number

 

 

요약

 

 

문자열 S가 주어질 때, 제시한 조건에 부합하는지 판단한다.

---

다음 조건들을 차례로 판별한다.
- S의 길이가 8인가?
- S의 첫 문자와 끝 문자가 알파벳 대문자에 해당하는가?
- S의 1 ~ 6 index의 문자열을 숫자로 바꾸었을 때 100000 ~ 999999에 속하는가?

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

string S;

int stoint(string s);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> S;
	if (S.length() != 8) {
		cout << "No";
		return 0;
	}
	if (!(S[0] >= 'A' && S[0] <= 'Z')) {
		cout << "No";
		return 0;
	}
	if (!(S[7] >= 'A' && S[7] <= 'Z')) {
		cout << "No";
		return 0;
	}
	string num = "";
	for (int i = 1; i <= 6; i++) num += S[i];
	int n = stoint(num);
	if (!(n >= 100000 && n <= 999999)) {
		cout << "No";
		return 0;
	}
	cout << "Yes";
	return 0;
}

int stoint(string s) {
	int ret = 0;
	for (int i = 0; i < s.length(); i++) {
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

 

 

 

C. Circular Playlist

 

 

요약

 

 

노래 N곡과 각 노래의 길이가 주어진다. N번째 노래가 끝난 뒤에는 1번째 노래가 다시 틀어진다고 할 때, 시간 T에는 어떤 노래가 몇 분째 틀어지고 있는지를 구한다.

---

1. N개의 노래에 대해 누적합을 psum[i]에 저장한다.

2. 만약 T가 psum[N] 보다 크다면, N곡의 노래를 한 번 이상 순회할 것이므로, T를 psum[N]으로 나눈 나머지에 대해서 생각한다.

 

3. psum[1] ~ psum[N]을 탐색하면서, psum[i]가 T보다 커지는 순간을 찾는다.

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

ll N, T;
ll arr[100001];
ll psum[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> T;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		psum[i] = psum[i - 1] + arr[i];
	}
	if (T > psum[N]) T %= psum[N];
	for (int i = 1; i <= N; i++) {
		if (T < psum[i]) {
			cout << i << " " << T - psum[i - 1];
			return 0;
		}
	}
	return 0;
}

 

 

 

D. Factorial and Multiple

 

 

요약

 

 

0이 아닌 정수 N개로 이루어진 수열 S가 주어진다. 그 중 K개를 택하여 만든 수열의 합이 D의 배수인 것 중 최대값을 구한다.

---

1. 우선, 수열에 mod D를 처리한 배열 remain[i]를 저장한다. remain[i]의 합에 mod D를 취한 값이 0이면 조건을 만족한다.

 

2. DP로 풀이한다. table[i][j][k]를 i번째 원소까지 j개의 원소를 택했고, 나머지가 k일 때 최대값을 저장한다.

점화식은 다음과 같다.
$DP(i,j,k) = max(DP(i+1, j, k), DP(i+1, j+1, (k + remain[i+1]) % D) + arr[i+1])$

 

3. N번째 원소에 도달했을 때, K개의 원소가 선택되지 않았거나 D의 배수가 아닌 경우 -INF값을 반환하여 정답을 구한다.

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

int N, K, D;
ll arr[101];
ll remain[101];
ll table[101][101][101];

ll DP(int now, int num, int re);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K >> D;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		remain[i] = arr[i] % D;
	}
	memset(table, -1, sizeof(table));
	if (DP(0, 0, 0) < 0) cout << -1;
	else cout << DP(0, 0, 0);
	return 0;
}

ll DP(int now, int num, int re) {
	if (now == N) {
		if (num == K) {
			if (re == 0) return 0;
			else return -INF;
		}
		else return -INF;
	}
	ll& ret = table[now][num][re];
	if (ret != -1) return ret;
	ret = max(DP(now + 1, num, re), DP(now + 1, num + 1, (re + remain[now + 1]) % D) + arr[now + 1]);
	return ret;
}

 

 

 

E. Least Elements

 

 

요약

 

 

자연수 N개로 이루어진 수열 A와 M, K가 주어진다. 시작점이 1 ~ N -M + 1인 모든 경우에 대하여 M개의 숫자로 이루어진 연속된 수열에서 가장 작은 K개의 원소의 합을 구한다.

---

1. 구간에서 가장 작은 K개의 원소의 합을 구하기 위해서는 세 가지 변수를 관리해주어야 한다.

- K개의 원소에 포함되어 있는 인덱스 값

- K개의 원소에 포함되어 있는 값

- K개의 원소에 포함되어 있지 않지만, 구간 내에 포함되어 있는 값

 

2. 시작점이 오른쪽으로 1 이동할때마다 다음을 고려하여 갱신한다.

- K개의 원소에 유효하지 않은 인덱스가 포함되어있는가?

- 만약 삭제된 원소가 있다면, 어떤 값이 추가되어야 하는가?

- 새로 합류한 원소가 기존 K개에 속한 값보다 작은 값인가?

 

3. set 자료구조를 이용하여 K개에 속한 원소의 값과 인덱스를 관리하고, 우선순위 큐 자료구조를 이용하여 후보 값들을 관리한다.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int N, M, K;
long long sum;
int arr[200000];
set <pii> idx, val;
priority_queue <pii, vector<pii>, greater<pii>> cand;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) {
		if (i < K) {
			sum += arr[i];
			idx.insert({ i, arr[i] });
			val.insert({ arr[i],i });
		}
		else {
			cand.push({ arr[i],i });
			pii m = *(idx.begin());
			if (m.first <= i - M) {
				sum -= m.second;
				idx.erase(m);
				val.erase({ m.second, m.first });
			}
			if (val.size() < K) {
				while (cand.size()) {
					if (cand.top().second <= i - M) cand.pop();
					else break;
				}
				val.insert(cand.top());
				idx.insert({ cand.top().second, cand.top().first });
				sum += cand.top().first;
				cand.pop();
			}
			while (cand.size()) {
				if (cand.top().second <= i - M) cand.pop();
				else break;
			}
			if (cand.size()) {
				pii M = *(val.rbegin());
				if (cand.top().first < M.first) {
					val.insert(cand.top());
					idx.insert({ cand.top().second, cand.top().first });
					sum += cand.top().first;
					cand.pop();
					cand.push(M);
					val.erase(M);
					idx.erase({ M.second, M.first });
					sum -= M.first;
				}
			}
		}
		if (i >= M - 1) cout << sum << " ";
	}
	return 0;
}

 

 

 

F. Xor Minimization

 

 

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

int N;

int func(vector <int> arr, int bit);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	vector <int> arr(N);
	for (int i = 0; i < N; i++) cin >> arr[i];
	cout << func(arr, 30);
	return 0;
}

int func(vector <int> arr, int bit) {
	if (bit < 0) return 0;
	vector <int> A, B;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] & (1 << bit)) A.push_back(arr[i]);
		else B.push_back(arr[i]);
	}
	if (A.size() == 0) return func(B, bit - 1);
	if (B.size() == 0) return func(A, bit - 1);
	return min(func(A, bit - 1), func(B, bit - 1)) + (1 << bit);
}