AtCoder Beginner Contest 171 후기

https://atcoder.jp/contests/abc171

AtCoder Beginner Contest 171 - AtCoder

 

---

이번 대회는 난이도 배분이 살짝 잘못된 것 같은 인상을 받았습니다. 대회 시간이 1시간 40분인데 앞의 5개 문제를 40분 정도에 다 풀고 남은 시간 동안 마지막 1개 문제를 풀었어야 했는데 하필 개념 모르면 절대 못 푸는 조합론 문제가 나와서..

스코어보드를 보니 저같은 사람이 한둘이 아닌 것 같았습니다 ;)  조합론이나 트리 문제들 같은 건 꾸준히 킬러 문제로 대회에서 나와 괴롭히는데 언젠간 몰아서 공부하리라 하곤 다시 보지 못했습니다.

A-생략합니다.

B-정렬해서 앞의 K개만 더하면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int>v(N);
	for (auto&i : v)cin >> i;
	sort(v.begin(), v.end());
	int sum = 0;
	for (int i = 0; i < K; i++)
		sum += v[i];
	cout << sum;
}

 

C-꽤 익숙한 문제인데 푼적은 없는 것 같은 이상한 문제입니다.. N진법으로 표현하기 같은 느낌으로 접근하시면 됩니다. 입력 범위를 꼭 확인하고 long long 형을 사용하여 1번 만에 AC를 받는 게 중요했습니다.

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

string change(ll n) {
	string ret;
	while (--n >= 0) {
		ret.push_back('a'+ n % 26);
		n /= 26;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

int main()
{
	ll n;
	cin >> n;
	string ans = change(n);
	for (auto i : ans)
		cout << i;
}

 

D-살짝은 당황한 문제입니다. 하지만 사용되는 수의 max값이 10^5이기때문에 충분히 배열로 수의 개수를 관리해주면서 합계를 연산해 주면 됩니다. 좋은 문제였네요. 마찬가지로 연산 중간에 int형을 넘어갈 수 있기 때문에 유의해줍시다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 2;
int arr[MAX_N] = { 0, };
ll sum = 0;

int main()
{
	int N;
	cin >> N;
	while (N--) {
		int tmp;
		cin >> tmp;
		arr[tmp]++;
		sum += tmp;
	}
	int Q;
	cin >> Q;
	while (Q--) {
		int a, b;
		cin >> a >> b;
		sum -= (ll)arr[a] * a;
		arr[b] += arr[a];
		sum += (ll)arr[a] * b;
		arr[a] = 0;
		cout << sum << "\n";
	}

}

 

E- xor연산도 코드포스,엣코더류 대회 단골 문제입니다. 심심하면 출제가 되는데.. xor연산의 몇 가지 특징 중에 하나는 암호화와 복호화라고 알고 있습니다. a, b라는 숫자가 있을 때 c=a^b라 하면(^연산=xor연산), c^a=b, c^b=a가 성립합니다. 이를 비슷하게 사용하면 답을 도출하지 않을까? 해서 시도한 게 모든 수를 xor 한 값을 N이라고 하고, 그 N에 해당 수 를 또 xor 연산한 값이 답으로 나오는 걸 알 수 있었습니다. 1분 1초가 아까운 대회에서 증명은 사치입니다. 그대로 코드를 짜서 제출하니 AC가 떴습니다. 자세한 설명은 엣 코더 사이트의 에디튜리얼에 써져있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
int main()
{
	int N, bits = 0;
	cin >> N;
	vector<int>v(N);
	for (auto&i : v) {
		cin >> i;
		bits ^= i;
	}
	for (auto i : v) {
		cout << (bits^i) << " ";
	}
}

 

F-추가 예정