2020 중앙대학교 프로그래밍 경진대회 (CPC) open contest에 참여했다.
본 대회랑 동시에 진행되었는데, 중간에 백준 사이트가 한 시간 정도 터져서 대회 주최자분들이 매우 안타까웠다....
대회의 초반 절반정도는 거의 다 구현 문제였다.
그런데 생각보다 구현하기가 까다로워서 스코어보드 상에서도 많은 WA를 볼 수 있었다.
나도 제대로 말려버렸다 ㅠ
[대회 문제] : www.acmicpc.net/category/detail/2345
[스코어보드]
[풀이]
(20.11.24 기준 난이도)
A. 교수님 그림이 깨지는데요? (Bronze 1)
- 문제에서 시키는대로 하면 된다. 가로로 K배, 세로로 K배의 개수만큼 출력해주면 된다.
#include<bits/stdc++.h>
using namespace std;
int A[11][11];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, K; cin >> N >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) cin >> A[i][j];
}
for (int i = 0; i < N*K; i++) {
for (int j = 0; j < N*K; j++) cout << A[i / K][j / K] << ' ';
cout << '\n';
}
}
B. 푸앙이가 길을 건너간 이유 (Silver 2)
수학 문제이다.
직선이 사각형을 통과하기 위해서는 사각형의 네 꼭짓점 중에서 직선을 기준으로 서로 반대편에 존재하는 두 꼭짓점이 존재해야 한다.
직선의 방정식이 주어질 때, 서로 반대편에 존재하기 위해서는 꼭짓점의 좌표를 직선의 방정식에 대입했을 때 부호가 서로 달라야 한다. (0은 제외)
의외로 생각보다 사람들이 이 풀이를 쉽게 생각해내지 못했던 것 같다. 아무도 제출을 안 했길래 처음엔 내가 너무 쉽게 생각했나 싶었다.... 퍼솔 하나 건져가서 다행이다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
ll A, B, C; cin >> A >> B >> C;
ll x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
vector<ll> v(5);
v[1] = A*x1 + B*y1 + C;
v[2] = A*x2 + B*y1 + C;
v[3] = A*x1 + B*y2 + C;
v[4] = A*x2 + B*y2 + C;
int c1 = 0;
int c2 = 0;
for (int i = 1; i <= 4; i++) {
if (v[i] < 0) c1++;
else if (v[i] > 0) c2++;
}
if (c1 > 0 && c2 > 0) cout << "Poor";
else cout << "Lucky";
}
C. 달력 (Silver 1)
365일을 표현하는 배열에다가 일정이 들어올 때 마다 해당되는 날짜에 1을 더해주면 된다.
그리고 연속된 구간에서의 최댓값*구간의 길이를 더해주면 답이 된다.
open 대회때에는 약간 복잡하게 스위핑을 구현해서 조금 어렵게 풀었는데, 생각보다 간단했다.
#include<bits/stdc++.h>
using namespace std;
int A[370];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
for (int i = 1; i <= N; i++) {
int s, e; cin >> s >> e;
for (int j = s; j <= e; j++) A[j]++;
}
int now = 0;
int cnt = 0;
int ans = 0;
for (int i = 1; i <= 365; i++) {
if (A[i] > 0) {
cnt++;
now = max(now, A[i]);
}
else {
ans += now*cnt;
now = cnt = 0;
}
}
ans += now*cnt;
cout << ans;
}
D. 진우의 민트초코우유 (Gold 5)
주어지는 민트초코우유가 최대 10개이므로 각 지점들을 방문하는 모든 순서를 다 고려해도 10!으로 충분하다.
따라서 next_permutation으로 모든 경우들을 고려한다.
각 경우마다 순서대로 마을을 방문하면서, 집으로 돌아갈 수 있을 때까지 방문하여 최댓값을 갱신해준다.
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int A[11][11];
int ans = 0;
int N, M, H;
int dist(pii a, pii b) {
return abs(a.first - b.first) + abs(a.second - b.second);
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
cin >> N >> M >> H;
vector<pii> milk;
pii S;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> A[i][j];
if (A[i][j] == 1) {
S.first = i;
S.second = j;
}
else if (A[i][j] == 2) {
milk.push_back({ i, j });
}
}
}
do {
int now = M;
for (int i = 0; i < sz(milk); i++) {
if (i == 0) {
if (dist(S, milk[i]) <= now) {
now -= dist(S, { milk[i] });
now += H;
if (dist(S, milk[i]) <= now) ans = max(ans, i + 1);
}
else break;
}
else {
if (dist(milk[i - 1], milk[i]) <= now) {
now -= dist(milk[i - 1], { milk[i] });
now += H;
if (dist(S, milk[i]) <= now) ans = max(ans, i + 1);
}
else break;
}
}
} while (next_permutation(all(milk)));
cout << ans;
}
E. 스트레이트 스위치 게임 (Gold 3)
각 스위치별로 연결된 큐브가 있고, 스위치를 누르면 스위치의 번호만큼 큐브의 숫자가 증가한다.
이때, 큐브의 숫자는 항상 0~4의 값을 가지게 되므로 스위치를 5번 누른 것과 0번 누른 것이 동일하다.
따라서 각 스위치를 0~4번 누른 모든 경우의 수, 최대 $5^8$개의 경우의 수가 존재하므로 완전 탐색으로 답을 구할 수 있다.
open 대회 때에는 계속해서 5로 나눠주는 방식이 아니라, 최종적으로 5로 나누어서 같은지 체크했었는데, 계속 WA를 받았다. 대회가 끝나고도 왜 틀렸는지 결국 찾지는 못했다.....
#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e9;
int N, K;
int A[10];
vector<vector<int>> swi;
int ans = MAX;
void sol(int idx, int cnt) {
if (idx > K) {
bool check = true;
for (int i = 2; i <= N; i++) {
if (A[1] != A[i]) check = false;
}
if (check) {
ans = min(ans, cnt);
}
return;
}
sol(idx + 1, cnt);
for (int i = 1; i <= 4; i++) {
for (int j : swi[idx]) A[j] = (A[j] + idx) % 5;
sol(idx + 1, cnt + i);
}
for (int j : swi[idx]) A[j] = (A[j] - idx * 4 + 100000) % 5;
return;
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> A[i];
swi.assign(K + 1, vector<int>());
for (int i = 1; i <= K; i++) {
int n; cin >> n;
while (n--) {
int a; cin >> a;
swi[i].push_back(a);
}
}
sol(1, 0);
if (ans == MAX) cout << -1;
else cout << ans;
}
이 풀이 말고도 edenooo님의 BFS 풀이도 있었다. 큐브의 가능한 모든 상태를 하나의 정점으로 표현하고, 각 스위치를 눌렀을 때 서로 연결되는 상태들을 간선으로 연결해주었다.
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int A[10];
int p5[10];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, K; cin >> N >> K;
vector<vector<int>> adj(625 * 625, vector<int>());
vector<vector<int>> swi(10, vector<int>());
int S = 0;
p5[0] = 1;
for (int i = 1; i <= N; i++) p5[i] = p5[i - 1] * 5;
for (int i = 1; i <= N; i++) {
cin >> A[i];
S += A[i] * p5[i - 1];
}
for (int i = 1; i <= K; i++) {
int a; cin >> a;
while (a--) {
int b; cin >> b;
swi[i].push_back(b);
}
}
for (int i = 0; i < p5[N]; i++) {
vector<int> tmp(10);
vector<int> tmp2;
int k = i;
int idx = 1;
while (k > 0) {
tmp[idx] = k % 5;
k /= 5;
idx++;
}
for (int j = 1; j <= K; j++) {
tmp2 = tmp;
for (int q : swi[j]) tmp2[q] += j;
int val = 0;
for (int q = 1; q <= N; q++) val += (tmp2[q] % 5)*p5[q - 1];
adj[i].push_back(val);
}
}
vector<int> dis(625 * 625, MAX);
queue<pii> q;
dis[S] = 0;
q.push({ S, 0 });
while (!q.empty()) {
int now = q.front().first;
int d = q.front().second; q.pop();
if (d > dis[now]) continue;
for (int v : adj[now]) {
if (dis[now] + 1 < dis[v]) {
dis[v] = dis[now] + 1;
q.push({ v, dis[v] });
}
}
}
int ans = MAX;
int tmp = 0;
for (int i = 1; i <= N; i++) {
tmp += p5[i-1];
}
for (int i = 0; i <= 4; i++) {
ans = min(ans, dis[i*tmp]);
}
if(ans != MAX) cout << ans;
else cout << -1;
}
F. 파일 탐색기 (Gold 2)
구현하기 꽤 까다로운 문제이다.
문자열들을 정렬하는 기준을 새로 만들어야 하는데, 문제가 되는 부분은 문자열 사이에 들어있는 숫자이다.
두 알파벳 사이에 1개 이상의 숫자가 들어있다면, 그 수를 10진수로 생각해서 비교를 해주어야 한다.
ex) abe012ff340w00 -> a / b / e / 012 / f / f / 340 / w / 00
그리고 10진수들을 정렬하는 기준을 만들어 준다.
원래의 10진수(ori) , 앞의 0을 제거한 10진수(no0) , 제거한 0의 개수(zero), no0의 길이 (len)를 저장하여,
no0의 길이가 다르면 길이가 긴 수가 무조건 더 크다.
no0의 길이가 같으면, 0을 제거한 10진수가 서로 같을 땐 zero를 비교하고, 다를 땐 no0의 사전순으로 정렬한다.
이렇게 10진수를 정렬한 후, 우선순위를 매겨서 실제 문자열에서 10진수 대신에 부여된 우선순위를 넣어준다.
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
struct s {
string ori;
string no0;
int zero;
int len;
};
bool cmp(s s1, s s2) {
if (s1.len == s2.len) {
if (s1.no0 == s2.no0) {
return s1.zero < s2.zero;
}
else return s1.no0 < s2.no0;
}
else {
return s1.len < s2.len;
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
vector<vector<int>>v(N + 1);
vector<string> st(N + 1);
vector<s> vc;
for (int i = 1; i <= N; i++) {
cin >> st[i];
string num, num2;
int cnt = 0;
bool check = false;
for (int j = 0; j < sz(st[i]); j++) {
if (st[i][j] == '0' && check == false) {
cnt++;
num2 += st[i][j];
}
else if ((st[i][j] == '0' && check) || (st[i][j] >= '1' && st[i][j] <= '9')) {
check = true;
num += st[i][j];
num2 += st[i][j];
}
else {
if (sz(num2) >= 1) vc.push_back({ num2, num, cnt, sz(num) });
num.clear();
num2.clear();
cnt = 0;
check = false;
}
}
if (sz(num2) >= 1) vc.push_back({ num2, num, cnt, sz(num) });
}
sort(all(vc), cmp);
map<string, int> mp;
int val = -MAX;
for (int i = 0; i < sz(vc); i++) {
mp[vc[i].ori] = val++;
}
map<vector<int>, int> mp2;
for (int i = 1; i <= N; i++) {
string num;
for (int j = 0; j < sz(st[i]); j++) {
if (st[i][j] >= '0' && st[i][j] <= '9') {
num += st[i][j];
}
else {
if (!num.empty()) v[i].push_back(mp[num]);
num.clear();
if (st[i][j] >= 'A' && st[i][j] <= 'Z') {
v[i].push_back((st[i][j] - 'A') * 2 - 1);
}
else if (st[i][j] >= 'a' && st[i][j] <= 'z') {
v[i].push_back((st[i][j] - 'a') * 2);
}
}
}
if (!num.empty()) v[i].push_back(mp[num]);
mp2[v[i]] = i;
}
sort(v.begin() + 1, v.end());
for (int i = 1; i <= N; i++) {
cout << st[mp2[v[i]]] << '\n';
}
}
G. 게임 개발자 영우 (Platinum 2)
너무 어려운 문제다.. 풀이가 궁금하다면 검수진에 참여하셨던 gratus님의 블로그에서 확인할 수 있다.
2020 중앙대학교 프로그래밍 대회 (CPC) 검수후기 / 풀이
www.acmicpc.net/category/detail/2345 처음으로 대회 검수에 들어가 보는 경험이 되었다. 서버 이슈가 약간 아쉽지만 출제하신 분들이 정말 많이 노력해 주셔서, 검수 및 풀이 과정은 재밌었다. 전체적인
gratus907.com
H. 나무는 쿼리를 싫어해~ (Platinum 2)
언뜻보면 Lazy Segment Tree의 기본 문제로 보이나, 배열의 크기가 너무 크다.
출제자의 의도는 좌표 압축 + 레이지 세그라고 하지만, 대부분의 참가자나 검수진들은 동적 레이지 세그 (Dynamic + Lazy Segment Tree)로 풀었다고 한다.
그래서 나는 출제자의 의도대로 풀어보았다. (절대 동적 세그를 몰라서 그러는건.........맞다..)
찾아보니 실제로 이용되는 노드의 수가 적을 때 동적 세그를 쓴다고 하는데 조만간 배워야 할 것 같다.
문제 풀이는 Lawali님의 도움을 많이 받았다. 라-멘
우선 쿼리를 보면 순서대로 수행되지 않는 것을 쉽게 알 수 있다. 따라서 오프라인으로 처리를 해주어야 한다.
오프라인으로 처리를 할 수 있다면, 좌표 압축이 가능하므로 주어지는 쿼리의 좌표들을 압축해주면 된다.
이때, 업데이트가 구간으로 정의가 되기 때문에 압축을 하고 나서 세그 트리의 leaf는 정렬된 상태에서 '현재 좌표 ~ 그다음 좌표까지의 구간'을 담게 된다.
압축된 좌표의 배열을 P라고 한다면, leaf는 [P[i] , P[i+1]) 을 의미하게 된다.
여기서 주의해야 할 점이 있다.
예를 들어서 [10, 30] update, [50, 60] update, [20, 50] sum 세 쿼리가 들어온다고 하자.
그러면 좌표들을 모으면 (10, 20, 30, 50, 60)으로 나오게 되고 이를 단순히 압축하면 P = {1, 2, 3, 4, 5} 이 된다.
이때, 여기서 생기는 문제점은 [20, 50]의 sum을 구하기 위해서 압축된 좌표로 [2, 4] 쿼리를 구하면,
50에서 그다음 좌표까지의 구간을 포함시켜버리는 것이다.
따라서 좌표 압축을 시켜줄 때, 구간의 오른쪽 끝은 +1을 해서 넣어준다. 즉, [l, r]을 [l, r+1)로 만들어준다.
그러면 (10, 20, 31, 50, 51, 60)으로 나오고, 좌표 압축을 해서 P = {1, 2, 3, 4, 5, 6}으로 만들어주면
[20, 50] 쿼리를 구할 때 겹치지 않게 된다.
일반화하면, a, b가 실제 좌표이고 압축시킨 좌표를 P[a] , P[b]라고 하면,
leaf노드가 [ P[i], P[i+1] ) 를 나타내고, 업데이트가 [a , b]이면 [a, b+1)을 업데이트시켜줘야 하고,
그러므로 p[l] = a, p[r] = b+1이라면, [l, r-1]으로 쿼리를 계산해주어야 한다.
말로 설명하려니 매우 복잡하고 읽는 사람도 이해가 전혀 되지 않을 것 같다... 코드를 통해서 이해해보거나, 직접 예시를 만들어보기를 바란다.
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
using ll = long long;
ll tr[400001], lazy[400001];
ll ans[50001];
map<ll, ll> mp;
ll p[100001];
void update_lazy(int x, int s, int e);
ll sum(int x, int s, int e, int l, int r) {
update_lazy(x, s, e);
if (s > r || e < l) return 0;
else 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);
}
void update_lazy(int x, int s, int e) {
if (lazy[x] != 0) {
tr[x] += (p[e + 1] - p[s])*lazy[x]; // 구간 [ p[s], p[e+1] )
if (s != e) {
lazy[x * 2] += lazy[x];
lazy[x * 2 + 1] += lazy[x];
}
lazy[x] = 0;
}
}
void update_range(int x, int s, int e, int l, int r, ll val) {
update_lazy(x, s, e);
if (s > r || e < l) return;
if (s >= l && e <= r) {
tr[x] += (p[e + 1] - p[s])*val; // 구간 [ p[s], p[e+1] )
if (s != e) {
lazy[x * 2] += val;
lazy[x * 2 + 1] += val;
}
return;
}
update_range(x * 2, s, (s + e) / 2, l, r, val);
update_range(x * 2 + 1, (s + e) / 2+1, e, l, r, val);
tr[x] = tr[x * 2] + tr[x * 2 + 1];
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
int N; cin >> N;
int cnt = 1;
int cnt2 = 1;
vector<vector<ll>> query;
vector<ll> v;
for (int i = 1; i <= N; i++) {
ll a, b, c, d; cin >> a >> b >> c >> d;
v.push_back(b);
v.push_back(c+1); //[b, c+1) 로 쿼리 계산
if (a == 1) {
query.push_back({ cnt++, b, c, d });
}
else {
query.push_back({ d, MAX, b, c , cnt2++});
}
}
sort(all(query));
sort(all(v));
v.erase(unique(all(v)), v.end());
for (int i = 0; i < sz(v); i++) {
mp[v[i]] = i + 1;
p[i + 1] = v[i];
}
for (int i = 0; i < N; i++) {
int q1, q2, q3;
if (query[i][1] == MAX) { //쿼리2인 경우
ll k = sum(1, 1, 2 * N, mp[query[i][2]], mp[query[i][3]+1]-1); //[p[q2] , p[q3+1])
ans[query[i][4]] = k;
}
else {
update_range(1, 1, 2 * N, mp[query[i][1]], mp[query[i][2]+1]-1, query[i][3]);
}
}
for (int i = 1; i < cnt2; i++) cout << ans[i] << '\n';
}