[후기]
올해도 휴학생인 관계로 Open contest에 참여했다. 나도 본대회 나가고 싶다 ㅠ
재밌고 좋은 문제들이 많아서 아직 안 풀어봤다면 꼭 풀어보는 것을 추천한다.
오픈 컨테스트 시간이 총 7시간으로 되게 길어서 중간에 있는 코드포스 라운드 때문인가 싶었는데, 그냥 문제가 많았다..
Champion이랑 Master division에 공통되는 문제가 있는줄 알았는데, 각각 8문제에 open용 문제 2문제까지 총 18문제가 있었다.
나는 코포 라운드에 참여하느라 약 3시간 반정도 참여했는데, 본대회의 Champion Division에 참가했다면 빠른 3솔 ~ 느린 4솔정도 했지 않을까 싶다. 오히려 Master division에 참여했다면 더 낮은 성적을 거뒀을 것 같다. 아직 부족하다는 걸 많이 느꼈다...
사실 오픈전에 본대회 Champion division의 처참한(?) 스코어보드를 미리 봤었는데, 오픈 컨테스트에는 Champion division 문제가 당연히 뒤쪽에 배치된 줄 알고 이 난이도에 그 정도 스코어보드가 나온다고..?라고 생각했으나, 끝나고 나니 Champion division이 앞에 배치되어있더라.. 어쩐지 뭔가 이상하다 했다.
본대회의 Champion division에서 최상위권을 차지할 것이라고 개인적으로 예상했던 사람들이 생각보다 많이 말린 느낌이었다. 반면 Master division에서는 내 예상대로 결과가 나온 것 같다. Master division의 수상자들이 Champion division에 나왔어도 아마 비슷한 등수를 얻지 않았을까 싶다. 신입생분들의 실력이 정말 대단하다고 생각하고 시간이 많이 남은 만큼 미래가 더욱 기대되는 분들이다.
('그 팀'이 돌아오는 2023년엔 ICPC 경쟁이 정말 치열하지 않을까 생각한다... 서강대 월파를 기원..!)
[풀이]
깔끔한 풀이나 정해를 보고 싶다면 공식 사이트 (acm.sogang.ac.kr/)를 참고하기를 바란다.
A. 파일 정리 (Champion div. A)
문제에서 시키는대로 구현하면 된다.
개인적으로 문자열을 다루는 것에 많이 익숙하지가 않아서 string의 메서드를 이용하지 않았는데, 공부를 할 필요가 있을 것 같다.
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
vector<string> v;
for (int i = 1; i <= N; i++) {
string s; cin >> s;
string tmp = "";
for (int j = sz(s) - 1; j >= 0; j--) {
if (s[j] == '.') break;
tmp = s[j] + tmp;
}
v.push_back(tmp);
}
sort(all(v));
int cnt = 1;
for (int i = 1; i < sz(v); i++) {
if (v[i] != v[i - 1]) {
cout << v[i - 1] << ' ' << cnt << '\n';
cnt = 1;
}
else cnt++;
}
cout << v[sz(v) - 1] << ' ' << cnt;
}
B. 컨설팅 (Champion div. B)
문제가 발생할 수 있는 경우가 생길때마다 직전에 WAIT를 넣어주면 된다.
WAIT를 추가하면 WAIT 이전의 명령어들은 이후에 아무런 영향을 주지 않는다는 점을 통해서 map을 이용해
마지막 WAIT 이후에 나온 명령어들을 저장해 두고, WAIT가 나오면 map을 초기화해준다.
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//mp1 : write의 a, mp2 : write의 b , mp3 : read의 a, w : write의 전체 문장
map<string, int> mp1, mp2, mp3, w;
vector<vector<string>> ans;
while (1) {
string s; cin >> s;
if (s == "EXIT") break;
else if (s == "WRITE") {
string a, tmp, b; cin >> a >> tmp >> b;
if (mp1[b] > 0 || mp2[b]>0 || mp2[a] > 0 || mp3[b] > 0
|| w[s + a + tmp + b] > 0 || w[s + b + tmp + a] > 0) {
ans.push_back({ "WAIT" });
ans.push_back({ s,a, tmp, b });
mp1.clear(); mp2.clear(); mp3.clear(); w.clear();
mp1[a] = 1; mp2[b] = 1;
w[s + a + tmp + b] = 1;
}
else {
ans.push_back({ s, a, tmp , b });
mp1[a]++; mp2[b]++;
w[s + a + tmp + b] = 1;
}
}
else {
string a; cin >> a;
if (mp2[a] > 0) {
ans.push_back({ "WAIT" });
ans.push_back({ s, a });
mp1.clear(); mp2.clear(); mp3.clear(); w.clear();
mp3[a]++;
}
else {
ans.push_back({ s, a });
mp3[a]++;
}
}
}
for (int i = 0; i < sz(ans); i++) {
for (string st : ans[i]) cout << st << ' ';
cout << '\n';
}
cout << "EXIT";
}
C. 연료가 부족해 (Champion div. C)
도착지점 (R, C)부터 시작해서 시작지점 (1, 1)으로 거꾸로 가면서, 주유소가 나올 때마다 지금까지 이용해온 연료를 최대한 감소시켜준다. 그렇게 되면 dp[1][1]이 도착지점까지 가는데 필요한 최소 연료 양으로 나오게 된다.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e9;
int A[3001][3001];
int dp[3001][3001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int R, C, N; cin >> R >> C>>N;
for (int i = 1; i <= N; i++) {
int a, b, c; cin >> a >> b >> c;
A[a][b] = c;
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) dp[i][j] = MAX;
}
dp[R][C] = 0;
for (int i = R; i >= 1; i--) {
for (int j = C; j >= 1; j--) {
if (i < R) dp[i][j] = min(max(dp[i + 1][j] + 1 - A[i][j], 0), dp[i][j]);
if (j < C) dp[i][j] = min(max(dp[i][j + 1] + 1 - A[i][j], 0), dp[i][j]);
}
}
cout << dp[1][1];
}
D. 에어컨 설치 (Champion div. D)
E. 사탕 배달 (Champion div. E)
F. 폰친구 (Champion div. F)
수-학 문제. 고등학생때 배운 중복 조합 문제의 대표적인 유형이다. 우여곡절 끝에 그래도 대회 도중에 풀었다.
예를 들어서 a + b + c = K 라는 식을 만족하는 (a, b, c)의 순서쌍의 개수를 구하는데, a, b, c에 제한이 걸려있는 경우이다.
이 문제에서는 각 사람이 m개 이상, M개 이하만큼 받을 수 있으므로 우선 m개씩 모두 분배해준다.
그러면 구해야 하는 방정식의 해는 $a_1 + a_2 + ... + a_n = K-Nm (a_i \leq M-m) $을 만족하는 순서쌍의 개수이다.
$a_i$ 의 범위를 신경쓰지 않는다면 $_NH_{K-Nm} $ 으로 전체 경우의 수가 나오고, 여기서 범위를 만족하지 않는 경우들을 제거해주어야 한다.
과정은 전체집합의 합집합을 구할 때, 교집합을 제거해주는 방식과 유사하다.
먼저 1명이 M-m보다 많이 받는 경우는, 1명에게 미리 M-m+1개를 나눠준 후, 나머지 사탕을 N명에게 나눠주는 경우와 같다.
따라서 1명을 고르는 경우의 수 $N$과 $_NH_{K-Nm-(M-m+1)}$ 의 곱을 빼주면 된다.
근데, 이렇게 되면 중복되는 경우가 생길 수 있다.
A를 고르고 B에도 M-m보다 많이 나눠주는 경우와 B를 고르고 A에도 M-m보다 많이 나눠주는 경우는 같은 경우이기 때문이다.
그러므로 2명 고르는 경우, 3명 고르는 경우, .... 다 고려를 해주어야 하고, 수식은 아래와 같이 나온다.
조합에 들어가는 범위가 크기 때문에 모듈로 역원 연산을 통해서 조합을 구해야 한다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
ll N, m, M, K;
#define MAX_C 1005000
ll fac[MAX_C + 1], facinv[MAX_C + 1];
ll mpow(ll a, ll x) { //a^x
ll res = 1;
while (x > 0) {
if (x % 2) res *= a;
res %= MOD;
a = (a*a) % MOD;
x /= 2;
}
return res;
}
void make_fac(void) {
fac[0] = 1;
for (int i = 1; i <= MAX_C; i++) fac[i] = (fac[i - 1] * i) % MOD;
facinv[MAX_C] = mpow(fac[MAX_C], MOD - 2);
for (int i = MAX_C - 1; i >= 0; i--) facinv[i] = facinv[i + 1] * (i + 1) % MOD;
}
ll combi(ll n, ll r) {
return (((fac[n] * facinv[r]) % MOD)*facinv[n - r]) % MOD;
}
ll H(ll n, ll r) {
return combi(n + r - 1, r);
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
cin >> N >> m >> M >> K;
K -= N*m;
M -= m;
make_fac();
ll ans = combi(N + K - 1, K);
for (int i = 1; i <= N; i++) {
if (K - (M + 1)*i >= 0) ans += (ll)pow(-1, i)*(H(N, K - (M + 1)*i)*combi(N, i))%MOD;
else break;
ans = (ans + MOD) % MOD;
}
cout << ans;
}
G. Confuzzle (Champion div. G)
H. 파인애플 피자 (Champion div. H)
I. 3대 측정 (Master div. A)
문제에서 나온대로 하면 된다.
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
int N, K, L; cin >> N >> K >> L;
vector<int> v;
for (int i = 1; i <= N; i++) {
int a, b, c; cin >> a >> b >> c;
if (a + b + c >= K && a >= L && b >= L && c >= L) {
v.push_back(a);
v.push_back(b);
v.push_back(c);
}
}
cout << sz(v) / 3 << '\n';
for (int a : v) cout << a << ' ';
}
J. 서강근육맨 (Master div B)
이분 탐색으로 해결 가능하다. 운동기구를 되도록이면 하루에 두 개를 사용하기로 했기 때문에, 이용하는 일 수는 (N+1)/2를 초과하면 안 된다.
따라서 M을 고정시켜놓으면 최대한 PT 기간이 짧도록 기구들을 짝을 지어준 후, PT기간이 (N+1)/2보다 크다면 M을 키워주고, 같으면 M을 작게 해서 다시 확인한다.
* 정렬시켜놓고 단순히 양끝에서 하나씩 이동시키면서 쌍을 지어줄 때의 최댓값으로 구해도 된다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll t[10001];
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++) cin >> t[i];
sort(t+1, t+1+N);
ll s = 0;
ll e = (ll)2*1e18;
ll ans = (ll)2*1e18;
while (s <= e) {
ll mid = (s + e) / 2;
int l = 1;
int r = N;
int tmp = 0;
if (t[N] > mid) {
s = mid + 1;
continue;
}
while (l <= r) {
if (l == r) {
tmp++;
break;
}
if (t[l] + t[r] > mid) {
tmp++;
r--;
}
else {
l++;
r--;
tmp++;
}
}
if (tmp > (N + 1) / 2) {
s = mid + 1;
}
else {
e = mid - 1;
ans = min(mid, ans);
}
}
cout << ans;
}
K. 반전 요세푸스 (Master div. C)
기존의 요세푸스 문제에서 추가된 문제이다.
처음에는 세그 트리를 이용해야 하는 줄 알았는데, 스코어보드에서 꽤 많이 풀린 걸 보고 다시 문제를 보니 N이 5000이었다.
덱을 이용해도 되고, 큐를 이용해도 된다.
K번째 수가 나올 때까지 나오는 수들은 모두 차례대로 뒤로 다시 넣어준다. 이를 이용해서 원형의 형태를 만들어 줄 수 있다.
M번 제거하고 나면, 방향을 바꿔주는데 현재 들어있는 원소들의 순서를 reverse 시켜줘도 되고, 방향을 바꿔도 된다.
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, K, M; cin >> N >> K >> M;
queue<int> q;
for (int i = 1; i <= N; i++) q.push(i);
int cnt = 0;
int cnt2 = 0;
while (!q.empty()) {
int a = q.front(); q.pop();
cnt++;
if (cnt == K) {
cout << a << '\n';
cnt = 0;
cnt2++;
if (cnt2 == M) {
vector<int> v;
while (!q.empty()) {
v.push_back(q.front()); q.pop();
}
for (int i = sz(v) - 1; i >= 0; i--) q.push(v[i]);
cnt2 = 0;
}
}
else q.push(a);
}
}
L. 민트 초코 (Master div. D)
곱하기가 나온 경우에는 뒤에 나오는 수가 분자에 들어가고, 나누기가 나온 경우에는 뒤에 나오는 수가 분모에 들어간다. 다만, 수를 직접 곱해준다면 long long의 범위도 벗어나므로, 소인수분해를 해서 분자와 분모가 각각 소수들을 몇 개 가지고 있는지 더해간다.
그리고 나서, 분자보다 분모에 어떤 소수가 더 많이 들어있다면 약분되지 않으므로 결과는 정수가 아닌 유리수가 된다.
(민트 초코는 싫다)
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int cnt[100001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N;
vector<int> v1, v2;
int a; cin >> a;
bool chk = false;
v1.push_back(a);
if (a == 0) chk = true;
for (int i = 1; i < N; i++) {
char c; cin >> c;
cin >> a;
if (a == 0) {
chk = true;
}
a = abs(a);
if (c == '/') v2.push_back(a);
else v1.push_back(a);
}
if (chk) {
cout << "mint chocolate";
return 0;
}
for (int i = 0; i < sz(v1); i++) {
int k = v1[i];
for (int j = 2; j*j <= v1[i]; j++) {
while (k>1) {
if (k%j == 0) {
cnt[j]++;
k /= j;
}
else break;
}
}
if (k > 1) cnt[k]++;
}
for (int i = 0; i < sz(v2); i++) {
int k = v2[i];
for (int j = 2; j*j <= v2[i]; j++) {
while (k>1) {
if (k%j == 0) {
cnt[j]--;
k /= j;
}
else break;
}
}
if (k > 1) cnt[k]--;
}
bool check = true;
for (int i = 1; i <= 100000; i++) if (cnt[i] < 0) check = false;
if (check) cout << "mint chocolate";
else cout << "toothpaste";
}
M. 할로윈의 양아치 (Master div. E)
서로 친구관계가 연결되면 모두 하나의 집합에 포함되기 때문에 Union-Find를 이용하여 친구들을 그룹 지어준다.
그리고 그 그룹에서 가지고 있는 모든 사탕의 개수와 사람의 수를 한 쌍으로 나타내면 무게와 가치가 있는 물건을 배낭에 넣는 Knapsack 문제로 바뀌게 된다.
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
using pii = pair<int, int>;
int c[30001];
pii P[30001];
int dp[3001];
int find(int a) {
if (P[a].first < 0) return a;
else return P[a].first = find(P[a].first);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (P[a].first > P[b].first) swap(a, b);
P[a].first += P[b].first;
P[a].second += P[b].second;
P[b].first = a;
}
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, M, K; cin >> N >> M >> K;
for (int i = 1; i <= N; i++) cin >> c[i];
for (int i = 1; i <= N; i++) {
P[i].first = -1;
P[i].second = c[i];
}
for (int i = 1; i <= M; i++) {
int a, b; cin >> a >> b;
merge(a, b);
}
vector<pii> v;
for (int i = 1; i <= N; i++) {
if (P[i].first < 0) {
v.push_back({ -P[i].first, P[i].second });
}
}
for (int i = 0; i < sz(v); i++) {
for (int j = K - 1; j >= v[i].first; j--) {
dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
}
}
int ans = 0;
for (int i = 1; i < K; i++) ans = max(ans, dp[i]);
cout << ans;
}
N. 비밀번호 제작 (Master div. F)
N이 100만 이하이므로, 각 수마다 하나의 정점이라고 생각한다.
그리고, 주어지는 비밀번호 값에 해당하는 정점은 거리를 0으로 두고, xor했을 때 하나의 bit만 켜지게 되는 두 정점 사이를 거리가 1인 간선으로 연결한다.
그 다음 BFS를 통해서 거리가 최대인 정점을 찾는다.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e9;
int dis[1000001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
int N; cin >> N;
int M; cin >> M;
fill(dis, dis + N + 1, MAX);
queue<int> q;
for (int i = 1; i <= M; i++) {
int a; cin >> a;
dis[a] = 0;
q.push(a);
}
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = 0; i < 20; i++) {
int next = now ^ (1 << i);
if (next >N || dis[next] != MAX) continue;
dis[next] = dis[now] + 1;
q.push(next);
}
}
int ans = 0;
for (int i = 0; i <= N; i++) {
ans = max(ans, dis[i]);
}
cout << ans;
}
O. 피보나치와 수열의 쿼리 (Master div. G)
P. 블랙홀 (Master div. H)
Q. RREF (Open A)
R. SPC 케이크 (Open B)
'프로그래밍 대회 풀이 > Sogang Programming Contest' 카테고리의 다른 글
| 2019 Sogang Programming Contest (Champion) 풀이 (0) | 2020.05.12 |
|---|