Semi-Game Cup 4 : Grand Final 이후 처음이자 전체 30번째로 참가하는 온사이트 프로그래밍 대회이다.
처음으로 참가하는 SCSCPC이지만(아무튼 SCPC로 합치면 3번째) 작년 대회때 Div.1의 경쟁률과 난이도에 대한 온갖 흉흉한 소문을 들었었고 교내대회가 아닌 동아리 대회더라도 참가제한도 없는데다 서울대는 매우 무서운 곳이기에 순위나 수상에 대한 부담 없이 대회를 치게 되었다. 당일 아침 출발과 함께 톡을 돌려보았는데 (내가 지인을 만드는 거의 유일한 창구인)ICPC팀을 같이 했던/하고있는 overnap님과 yyyy7089님은 둘다 등록은 했지만 아쉽게도 당일 일정이 생겨서 대회장에 오지 못한다고 하였다.
A번 CUBRID HA Load Balance - AC (+1 WA) - 19분 (+1) - 4위 (1 00 / 39)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
bool alive[2000];
int qt[2000], a[2000], b[2000], c[2000];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
fill(alive, alive + N, true);
for (int i = 0; i < Q; i++) {
cin >> qt[i] >> a[i];
if (qt[i] == 1) {
if (!alive[--a[i]]) a[i] = -1;
else alive[a[i]] = false;
}
else {
cin >> b[i] >> c[i];
}
}
int mans = 0, sans = 0, ans = 0, tans = 0;
for (int i = Q - 1; i >= 0; i--) {
if (qt[i] == 1) {
if (a[i] != -1) tans++;
}
else {
if (a[i] > mans) mans = a[i];
if (c[i] > sans) sans = c[i];
ans = max(ans, mans + sans);
if (a[i] + b[i] + c[i] > ans) ans = a[i] + b[i] + c[i];
if (ans && !mans) mans++;
ans = max(ans, mans + sans);
tans = max(ans, tans);
}
}
if (tans <= N) cout << ans << '\n';
else cout << "-1\n";
}
A번은 셋에서 가장 쉬운 문제로 유일하게 난이도 무작위 배치가 되지 않았음이 공지되었었다. 가장 쉬운 난이도의 문제 치고는 난이도가 상당히 있는 편이다.
Master 서버가 사라지면 Slave 서버중 하나가 Master서버로 바뀐다는 말은 서버가 1개 이상 있을경우 항상 Master서버가 존재해야 한다는 의미이다. 서버의 상태를 임의로 정하고 원하는 서버를 삭제할수 있기에 첫번째 Slave서버가 Master서버로 바뀌는 정보는 무시하여도 된다.
쿼리를 역순으로 보면서 3가지 task 각각에 대해 suffix에서의 최댓값을 찾는다면 해당 시점부터의 쿼리를 전부 처리하는 최소 서버수를 알수 있다. RO 요청은 어느 서버에서 실행되던 상관이 없으니 RW와 SO요청들을 먼저 서버에 배정한뒤 남은 서버들에 RO 요청을 채우고 RO요청을 처리할 서버가 부족한 경우에는 아직 상태가 정해지지 않은 서버를 추가로 만들면 된다.
서버 삭제 쿼리를 처리할때 마지막으로 들어온 삭제일경우에만 유효한 경우로 보는게 최적이고 이때 항상 전체 서버수를 하나 늘렸다가 WA를 받았다. 다시 생각해보니 삭제로 들어온 서버가 처음부터 켜져있지 않은 서버일수도 있어서 초기 Master서버, 초기 Slave 서버, 초기 켜져있을 전체 서버, 최소 전체 서버를 전부 관리하고 AC를 받았다.
1솔브 직후 시도가 가장 많던 C번을 고민하기 시작했고 순위가 계속 높고 스코어보드에서 새빨간 사람들이 몇명 말리고 있길래 살짝 희망이 들었다.
C번 SCSC Magical Garden - AC (+1 WA) - 64분 (+1) - 2위 (200 / 123)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
bool flower[100][100];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
/*for (int T = 3; T <= 100; T++) {
cout << "size : " << T << '\n';
for (int i = 0; i < 1 << 9; i++) {
int tco = 0;
for (int j = 0; j < T; j++) {
for (int k = 0; k < T; k++) {
flower[j][k] = i & (1 << ((j % 3) * 3 + k % 3));
if (flower[j][k]) tco++;
//if (i == 436 && T == 13) cout << flower[j][k];
}
//if (i == 436 && T == 13) cout << '\n';
}
if (i == 436 && T == 16) cout << T << ' ' << tco << '\n';
if (tco << 1 >= T * T) continue;
if (i == 436 && T == 16) {
cout << T << ' ' << tco << '\n';
for (int j = 0; j < T; j++) {
for (int k = 0; k < T; k++) cout << flower[j][k];
cout << '\n';
}
cout << '\n';
}
bool flag = true;
for (int j = 0; j + 2 < T; j++) {
for (int k = 0; k + 2 < T; k++) {
int tmp = 0;
for (int ji = j; ji <= j + 2; ji++) {
for (int ki = k; ki <= k + 2; ki++) {
tmp += flower[ji][ki];
}
}
if (tmp << 1 <= 3 * 3) {
flag = false;
//if (i == 436 && T == 13) cout << j << ' ' << k << '\n';
}
}
}
if (flag) {
cout << "YES " << i << '\n';
for (int j = 0; j < T; j++) {
for (int k = 0; k < T; k++) cout << flower[j][k] << ' ';
cout << '\n';
}
cout << '\n';
}
}
}*/
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
if (N == 4 || N == 5 || N == 7 || N == 8 || N == 10 || N == 11 || N == 13 || N == 14) {
cout << "YES\n";
if (N == 4) cout << "CSSC\nCSSC\nCSCC\nCSSC\n";
else if (N == 5) cout << "SCSSC\nCCSCC\nSSCSS\nSCSSC\nCCSCC\n";
else if (N == 7) cout << "CSSCSSC\nCSSCSSC\nCSCCSCC\nCSSCSSC\nCSSCSSC\nCSCCSCC\nCSSCSSC\n";
else if (N == 8) cout << "SCSSCSSC\nCCSCCSCC\nSCSSCSSC\nSCSSCSSC\nCCSCCSCC\nSCSSCSSC\nSCSSCSSC\nCCSCCSCC\n";
else if (N == 10) cout << "CSCCSCCSCC\nCSSCSSCSSC\nCSSCSSCSSC\nCSCCSCCSCC\nCSSCSSCSSC\nCSSCSSCSSC\nCSCCSCCSCC\nCSSCSSCSSC\nCSSCSSCSSC\nCSCCSCCSCC\n";
else if (N == 11) cout << "CCSCCSCCSCC\nCCSCCSCCSCC\nSSSSSSSSSSS\nCCSCCSCCSCC\nCCSCCSCCSCC\nSSSSSSSSSSS\nCCSCCSCCSCC\nCCSCCSCCSCC\nSSSSSSSSSSS\nCCSCCSCCSCC\nCCSCCSCCSCC\n";
else if (N == 13) cout << "CSCCSCCSCCSCC\nCSSCSSCSSCSSC\nCSSCSSCSSCSSC\nCSCCSCCSCCSCC\nCSSCSSCSSCSSC\nCSSCSSCSSCSSC\nCSCCSCCSCCSCC\nCSSCSSCSSCSSC\nCSSCSSCSSCSSC\nCSCCSCCSCCSCC\nCSSCSSCSSCSSC\nCSSCSSCSSCSSC\nCSCCSCCSCCSCC\n";
else if (N == 14) cout << "CCSCCSCCSCCSCC\nCCSCCSCCSCCSCC\nSSSSSSSSSSSSSS\nCCSCCSCCSCCSCC\nCCSCCSCCSCCSCC\nSSSSSSSSSSSSSS\nCCSCCSCCSCCSCC\nCCSCCSCCSCCSCC\nSSSSSSSSSSSSSS\nCCSCCSCCSCCSCC\nCCSCCSCCSCCSCC\nSSSSSSSSSSSSSS\nCCSCCSCCSCCSCC\nCCSCCSCCSCCSCC\n";
}
else cout << "NO\n";
}
}
처음에는 3-패리티로 0(mod3)은 답이 없고 1(mod3)은 예제대로, 2(mod3)만 구하면 되나 싶었지만 A번보다는 어려운 문제이고 스코어보드에서 틀린 제출이 너무 많길래(사실 Div.1에서는 가장 쉬운 A번을 포함해 모든 문제와 모든 참가자 쌍에 대해 한번에 맞는경우가 거의 없이 패널티가 난무했다) 이 방법은 통하지 않을것이 확실시되었다. 그래도 3*3이 반복되는건 맞아보였고 규칙을 찾기 위한 시뮬레이션 코드를 짜는 도중 3*3 9칸에 C4개, S5개로 S를 최소화하는것이 최적해라 가정하면 3*3이 확실히 반복된다는것을 알아냈다. 그리고 추가 증명은 하지 않았지만 전체 판에서 S를 최소화해야하니 불필요한 S를 추가로 넣는 답은 필요가 없다고 생각하고 넘겼다.
완성된 시뮬레이션 코드를 돌려보니 N > 10일때부터는 출력이 나오지 않기에 의아해하다 안쪽에서 S가 더 많은영역의 개수가 N^2에 비례하는데 가장자리에서 적절히 경계가 나누어져 C가 추가로 들어오는 경우는 N에 비례하기에 N이 너무 크면 답이 나오지 않는 이유를 알았고 그렇게 WA를 받았다.
틀린 접근인가 싶어서 20분을 더 고민하다 flower 배열을 10*10으로 선언한걸 찾았고 결국 11, 13, 14에서의 해를 추가로 찾았다.
다른 문제들에 비해 꽤 쉬운편에 속하는 A와 C를 풀고 솔브가 조금 있는 D와 J, K 그리고 제목에 자료구조와 함께 가장 자신있는 태그인 트리가 박혀있는 I번까지 네 문제를 전부 훑어보고 고민을 하기 시작했다. 그러다 J번의 솔브가 좀 나오기 시작했고 순위 자체는 상위권 수상을 노릴만 했기에 저점보다는 고점을 높여야 한다는 생각이 들어 한번 불완전한 아이디어라도 짜보기로 하였다.
J번 ChannelTalk Workflow - AC (+1 WA) - 115분 (+1) - 1위 (300 / 258)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int F[2048], L[2048], G[2048], M, N;
bool used[1001];
void mkmodule(int t1, int t2, int idx, int level) {
//cout << M << '\n';
F[idx] = (t1 + t2) >> 1;
if (level) {
bool flag = false;
for (int i = 1; i <= N; i++) {
if (!used[i] && (i < t1 || F[idx] < i)) {
used[i] = true;
flag = true;
L[idx] = i;
break;
}
}
if (!flag) L[idx] = M++;
if (M > 2048) {
cout << "-1\n";
exit(0);
}
mkmodule(t1, F[idx], L[idx], level - 1);
if (F[idx] + 1 <= t2) {
flag = false;
for (int i = 1; i <= N; i++) {
if (!used[i] && (i <= F[idx] || t2 < i)) {
used[i] = true;
flag = true;
G[idx] = i;
break;
}
}
if (!flag) G[idx] = M++;
if (M > 2048) {
cout << "-1\n";
exit(0);
}
mkmodule(F[idx] + 1, t2, G[idx], level - 1);
}
}
else {
L[idx] = t1;
G[idx] = t2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K;
cin >> N >> K;
if (K < 15 && (1 << (K - 1) < N)) {
cout << "-1\n";
return 0;
}
M = N + 1;
int root = 0;
while (K >= 3 && (K >= 15 || (1 << (K - 2) >= N))) {
K--;
F[root] = N;
L[root] = M++;
root = L[root];
}
mkmodule(1, N, root, K - 2);
cout << M << '\n';
for (int i = 0; i < M; i++) {
//cout << i << " : ";
cout << F[i] << ' ' << L[i] << ' ' << G[i] << '\n';
}
}
우선 문제 상태는 매우 분할정복을 쓰기 좋은 상태였고 각 모듈이 세그먼트 트리의 노드와 비슷하게 구간을 좌우 자식에 반씩 나눠 내려보내고 정해진 깊이만큼 리프에서 추가로 이동하였다. 예제 출력을 대회장 입장시에 받은 스폰서 제인 스트리트의 모눈종이노트와 펜으로 정리해보았다.(기하나 격자문제를 풀때는 좋겠지만 일반적인 수식이나 아이디어 정리를 하기에는 선명한 격자가 글자 식별을 방해하였다. 그러나 다행히 같이 받은 펜이 파란색이라 다행히도 모눈 위에 글을 적어도 잘 식별할수 있었다.) 답은 문제가 없었지만 N^2 정도의 모듈이 필요한 비효율적인 방식이라 최대 깊이를 미리 구한 뒤 루트를 필요한만큼 뺑이 돌리고 시작하는 3N모듈 정도의 해를 만들었고 여전히 모듈 부족으로 불가능한 경우가 있지만 일단 현제 풀이가 최적이라 생각하고 한번 제출을 해 보았다.
WA를 받았지만 앳코더라 데이터별 결과를 확인해 보았고 예제 포함 AC 62개, WA 6개로 대부분의 데이터를 통과해 전체 흐름은 맞고 엣지케이스만 처리하면 된다는 확신을 얻을수 있었다. 지문의 예제 출력을 한번 확인해보니 N개의 도착점 노드들을 대부분 활용한다는데서 힌트를 얻어 0, [N+1, M] 모듈들뿐 아닌 모든 모듈에서 분할정복을 처리할수 있는 방법을 찾아보기 시작했다. O(N^2) 시복이 도는 제한이니 매 분할정복마다 처리하는 질문 구간을 벗어난 도착점 모듈들을 전부 확인하여 아직 사용하지 않은 모듈들을 전부 활용하여서 효율을 높여 AC를 받았다.
이후 스코어보드를 확인하니 무려 1위를 하고있는 상태였고 오래 유지할 자신이 없어(처음이자 마지막으로 본 순위이다.) 바로 스코어보드를 캡쳐하여 저장해뒀다. F번과 I번도 제출이 나오기 시작하여 F번을 읽은 뒤 다른문제들은 답이 없어보여 늘상 그렇듯 태그편식을 하며 트리문제인 D번과 I번을 고민하기 시작했다. D번은 문제상황이 PS 초기에 푼 루비들중 하나인 Monster Hunter(Diamond I), Prospecting(Ruby V), Escape(Ruby V) 세 동일문제쌍과 비슷한것을 깨달았지만 추가로 떠오르는바가 없었고 I번을 잡았다.
I번 Tree, Game, and Query - AC (+2 WA) - 197분 (+2) - 7위(프리즈 시점) (400 / 495)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
vector<int> graph[300000];
int V[300000], subsz[300000], heavy[300000], dep[300000];
void szdfs(int node, int par) {
subsz[node] = 1;
for (int i : graph[node]) {
if (i == par) continue;
dep[i] = dep[node] + 1;
szdfs(i, node);
subsz[node] += subsz[i];
if (heavy[node] == -1 || subsz[heavy[node]] < subsz[i]) heavy[node] = i;
}
}
int nodeidx[300000], idxtonode[300000], nodetoline[300000], linefront[300000], linetop[300000];
int nodeco = 1, lineco = 1;
void hlddfs(int node, int par) {
if (heavy[node] != -1) {
nodeidx[heavy[node]] = nodeco;
idxtonode[nodeco] = heavy[node];
nodetoline[heavy[node]] = nodetoline[node];
nodeco++;
hlddfs(heavy[node], node);
}
for (int i : graph[node]) {
if (i == par || i == heavy[node]) continue;
nodeidx[i] = nodeco;
idxtonode[nodeco] = i;
nodetoline[i] = lineco;
linefront[lineco] = nodeco;
linetop[lineco] = node;
nodeco++;
lineco++;
hlddfs(i, node);
}
}
int oseg0[1048576], oseg1[1048576], eseg0[1048576], eseg1[1048576];
bool lazy[1048576];
#define lidx (idx << 1)
#define ridx (idx << 1 | 1)
void dolazy(bool push, int idx) {
if (lazy[idx]) {
swap(oseg0[idx], oseg1[idx]);
swap(eseg0[idx], eseg1[idx]);
if (push) {
lazy[lidx] ^= true;
lazy[ridx] ^= true;
}
lazy[idx] = false;
}
}
void init(int t1, int t2, int idx) {
if (t1 == t2) {
if (dep[idxtonode[t1]] & 1) oseg1[idx] = V[idxtonode[t1]];
else eseg1[idx] = V[idxtonode[t1]];
//cout << t1 + 1 << " : " << oseg1[idx] << ' ' << eseg1[idx] << '\n';
return;
}
int mid = (t1 + t2) >> 1;
init(t1, mid, lidx);
init(mid + 1, t2, ridx);
oseg0[idx] = oseg0[lidx] ^ oseg0[ridx];
oseg1[idx] = oseg1[lidx] ^ oseg1[ridx];
eseg0[idx] = eseg0[lidx] ^ eseg0[ridx];
eseg1[idx] = eseg1[lidx] ^ eseg1[ridx];
}
void update(int t1, int t2, int q1, int q2, int idx) {
dolazy(t1 < t2, idx);
if (q2 < t1 || t2 < q1) return;
if (q1 <= t1 && t2 <= q2) {
lazy[idx] = true;
dolazy(t1 < t2, idx);
return;
}
int mid = (t1 + t2) >> 1;
update(t1, mid, q1, q2, lidx);
update(mid + 1, t2, q1, q2, ridx);
oseg0[idx] = oseg0[lidx] ^ oseg0[ridx];
oseg1[idx] = oseg1[lidx] ^ oseg1[ridx];
eseg0[idx] = eseg0[lidx] ^ eseg0[ridx];
eseg1[idx] = eseg1[lidx] ^ eseg1[ridx];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
fill(heavy, heavy + N, -1);
for (int i = 0; i < N; i++) cin >> V[i];
for (int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
graph[--u].push_back(--v);
graph[v].push_back(u);
}
szdfs(0, -1);
hlddfs(0, -1);
init(0, N - 1, 1);
//for (int i = 0; i < N; i++) cout << i + 1 << " -> " << idxtonode[i] + 1 << '\n';
int root = 0;
//cout << oseg1[1] << '\n';
while (Q--) {
int qt;
cin >> qt;
if (qt == 1) {
int x, y;
cin >> x >> y;
x--;
y--;
while (true) {
if (nodetoline[x] == nodetoline[y]) {
if (nodeidx[x] > nodeidx[y]) swap(x, y);
update(0, N - 1, nodeidx[x], nodeidx[y], 1);
break;
}
else {
if (dep[idxtonode[linefront[nodetoline[x]]]] > dep[idxtonode[linefront[nodetoline[y]]]]) swap(x, y);
update(0, N - 1, linefront[nodetoline[y]], nodeidx[y], 1);
y = linetop[nodetoline[y]];
}
}
}
else {
int z;
cin >> z;
root = --z;
}
if (dep[root] & 1) {
if (eseg1[1]) cout << "Terra\n";
else cout << "Lulu\n";
}
else {
if (oseg1[1]) cout << "Terra\n";
else cout << "Lulu\n";
}
}
}
I번은 고민중 문득 얼마전 코포 또는 앳코더 라운드에서 틀린뒤 풀이를 들었던것 같은 2D grid 에서의 staircase nim 문제가 떠올랐다. 트리에서도 되는지는 잘 기억이 안나 검색을 통해 코드포스 블로그에서 I번과 같은 문제상황에서도 가능하다는것을 확인하였고 HLD로 적용할수 있다는것을 알아내어 바로 코드를 짰다.
무려 2번의 WA와 34분가량의 디버깅 끝에 heavy 경로의 시작점의 높이 비교시에 인덱스를 잘못 넣는 오류를 찾아냈고 결국 AC를 받았다.
4시간 대회중 3시간 시점에 프리즈가 되었고 당시 순위는 7위까지 내려와있었다. 그런데 K번 문제에서 특정 풀이 저격을 위해 데이터의 입력 제한을 늘렸는데 이를 지문에 반영하지 않았던 관계로 지문을 보고 짜서 틀린 참가자들이 있다는 공지가 나왔고 순차적으로 전체 대회 시간이 4시간에서 4시간 30분으로 늘어난 뒤, 피해를 본 세명의 참가자들에게는 피해를 본 정도의 차등에 따라 최대 5시간 10분까지 추가시간을 준다는 공지가 나왔다. D번의 방향은 잡혔지만 막막한 부분이 많았고 다른 문제들은 손을 대볼 생각도 못하고 있었기에 나에게 좋은 상황은 아니었다.
D번 Mobilint Tensor Scheduling (ARIES) - 2WA - 7위(프리즈 시점) (400 / 495)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll w[200000], b[200000], realw[200000], realb[200000];
bool isleaf[200000], merged[200000];
int p[200000], dsu[200000], deg[200000];
int find(int a) {
if (dsu[a] == a) return a;
return dsu[a] = find(dsu[a]);
}
struct cmp {
bool operator()(pair<pair<ll, ll>, int> ain, pair<pair<ll, ll>, int> bin) {
pii a = ain.first, b = bin.first;
if (a.first <= a.second) {
if (b.first <= b.second) return a.first > b.first;
else return false;
}
else {
if (b.first <= b.second) return true;
else return a.second < b.second;
}
}
};
vector<int> graph[200000];
int subsz[200000], dsusz[200000];
void szdfs(int node, int par) {
subsz[node] = 1;
for (int i : graph[node]) {
if (i == par) continue;
szdfs(i, node);
subsz[node] += subsz[i];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll M;
cin >> N >> M;
p[0] = -1;
fill(isleaf, isleaf + N, true);
fill(dsusz, dsusz + N, 1);
for (int i = 0; i < N; i++) {
cin >> w[i];
realw[i] = w[i];
dsu[i] = i;
}
fill(deg, deg + N, 1);
for (int i = 1; i < N; i++) {
cin >> p[i];
isleaf[--p[i]] = false;
b[p[i]] += w[i];
realb[p[i]] += w[i];
graph[p[i]].push_back(i);
deg[p[i]]++;
}
szdfs(0, -1);
ll answ = 0, ansb = 0, tmpw = 0;
priority_queue<pair<pair<ll, ll>, int>, vector<pair<pair<ll, ll>, int>>, cmp> pq;
for (int i = 1; i < N; i++) {
if (isleaf[i]) {
answ += w[i];
tmpw += w[i];
}
pq.push({{w[i], b[i]}, i});
}
/*cout << "w : ";
for (int i = 0; i < N; i++) {
if (merged[i]) cout << "m ";
else cout << w[i] << ' ';
}
cout << '\n';
cout << "b : ";
for (int i = 0; i < N; i++) {
if (merged[i]) cout << "m ";
else cout << b[i] << ' ';
}
cout << '\n';
cout << '\n';*/
vector<int> sta;
while (!pq.empty()) {
pair<pair<ll, ll>, int> tmp = pq.top();
pq.pop();
if (w[tmp.second] != tmp.first.first || b[tmp.second] != tmp.first.second || merged[tmp.second]) continue;
int par = find(p[tmp.second]);
ll tw = max(w[tmp.second], w[tmp.second] - b[tmp.second] + w[par]);
ll tb = b[tmp.second] + b[par] - w[tmp.second] - w[par] + tw;
w[par] = tw;
b[par] = tb;
dsu[find(tmp.second)] = par;
merged[tmp.second] = true;
if (par) pq.push({{w[par], b[par]}, par});
while (!--deg[tmp.second]) {
if (isleaf[tmp.second]) {
if (deg[p[tmp.second]] == 1) tmp.second = p[tmp.second];
else {
deg[p[tmp.second]]--;
break;
}
}
else {
answ = max(answ, tmpw + realw[tmp.second]);
tmpw -= realb[tmp.second];
//cout << tmp.second + 1 << " : " << answ << ' ' << tmpw << '\n';
if (deg[p[tmp.second]] == 1) tmp.second = p[tmp.second];
else {
deg[p[tmp.second]]--;
break;
}
}
}
/*cout << tmp.second + 1 << " -> " << par + 1 << '\n';
cout << "w : ";
for (int i = 0; i < N; i++) {
if (merged[i]) cout << "m ";
else cout << w[i] << ' ';
}
cout << '\n';
cout << "b : ";
for (int i = 0; i < N; i++) {
if (merged[i]) cout << "m ";
else cout << b[i] << ' ';
}
cout << '\n';
cout << '\n';*/
}
//for (int i = 0; i < N; i++) cout << deg[i] << ' ';
//cout << '\n';
if (answ <= M) cout << answ << '\n';
else cout << "OOM\n";
}
이 문제가 Monster Hunter와 유사하다는건 기억하지만 푼지 너무 오래되어 Monster Hunter의 풀이는 까먹었기에 검색을 하여 Monster Hunter 풀이글을 찾아보았고 또 검색 결과로 같이 나온 Faker's algorithm 설명글도 한번 보았다. Faker's algorithm에 대해 들어본적은 몇번 있었고 도입부의 이름이 지어진 경위도 읽어본적이 있지만 어디에 쓰이는 알고리즘인지는 몰랐었는데 이런 문제에 사용되는 알고리즘이라는것을 새로 알았다. Monster Hunter처럼 정렬 순서를 정해서 그냥 합쳐도 보고 리프를 포함하는 연결요소를 따로 관리해서 합쳐도 보았지만 익숙하지 않은 알고리즘이고 루트 -> 리프가 아닌 리프 -> 루트 순서기에 트리문제에서 익숙한 DFS / 트리DP식 사고도 힘들어 시간안에 해결하지 못했다.
4솔브 시점에 프리즈된 스코어보드 기준으로는 4위였어서 3시간 대회 1시간 프리즈를 생각하며 3-4등상인 버즈까지는 무리여도 5-10등상인 키보드는 노려볼만 하지 않을까란 희망을 가졌다. 그러나 문제이슈로 프리즈된 시간이 1시간 -> 1시간 30분 ~ 2시간 10분으로 대폭 증가하였고 초반에 말렸다 뒷문제로 만회한사람들도 좀 있어서(대표적으로 프리즈시점 3솔브, 최종 7솔브로 프리즈 된 이후 더 짧은 시간동안 더 어려운 문제들을 더 많이 풀고 거의 한페이지쯤 올라와서 우승한 dadas08님) 아쉽게 12위로 네이버페이 20,000원권을 받게 되었다.(네이버페이를 안써서 나중에 등록해야지 하고 까먹고 있었는데 후기 작성중에 이 사실이 기억나 다행히도 제대로 수령할 수 있었다.) 스코어보드 공개는 대회 운영진이 직접 짠 스팟보드로 진행되었다고 했는데 참가자가 매우 많아(당일 제출이 있는 참가자가 3개 디비전 합쳐서 223명) 매우 빠르게 진행되어 순위가 확정되는것만 보여주었고 프리즈 시간이 60분(추정)으로 설정된 뒤 틀린 제출은 전부 공개가 된 상태라 모든 프리즈된 제출이 맞는걸로 보이는 일이 있었다.
그리고 Div.1에 ibm 닉네임이 많이 보였다는 이야기를 들어 확인해보니 무려 6명(현재는 닉네임을 바꿔 확인이 불가능하지만 qwerasdfzxcl님도 ibm2005 닉네임으로 참가를 하였다.)에 그중에서도 ibm중 가장 순위가 높은 ibm2005, ibm중 가장 순위가 낮은 ibm2005, 대회장 안온 ibm2005 이렇게 ibm2005만 3명이나 있었다.
대회가 끝난 뒤에는 치르치르에서 뒷풀이가 있다고 하였는데 참가하기로 결정한뒤 위치를 찾아보았지만 누가 뒷풀이를 가는지 알지 못해 잠시 방황하다 가장 많은 사람이 뭉쳐있는곳을 따라갔고 다행히도 뒷풀이를 가는중이 맞았다. 버스를 타야하는 거리였는데 버스정류장에 기사도 없이 문만 열린 빈 버스가 있었고 일단 타야하는 버스가 맞았기에 우선 다같이 버스를 탄 뒤 기다리다 버스 출발까지 10분정도 남았다는것을 알게 되었다. 누가 버스를 탈취해서 운전할지에 대한 짧은 농담 끝에 기사님이 돌아오셔서 주말 저녁에 대학교에서 출발하는 버스가 출발 전부터 좌석뿐 아니라 서있을곳도 부족할정도로 가득 차있다는것에 충격을 먹으셔서 사람들이 행사가 있었다고 설명을 하였다.
치르치르에 도착을 한 이후에는 아무 테이블에 앉아 주변 사람들과 대화하며 저녁을 먹었다. 건너편 테이블에서는 세그먼트 트리 게임, XOR 게임, 큐 게임, 우큐(또는 우선순위 큐 또는 최대 힙) 게임등 난생 처음듣는 PS 자료구조 술게임을 즐기며 규칙을 정하는 소리가 간간히 들렸고 우리 테이블에서는 문제의 반쯤을 출제했다고 하는 terrasphere님이 있어서(다른 반쯤은 sorohue님이 출제하셨다고 한다.) 테라와 루루가 테라와 콜라와 사이다와 치르치르미치르를 먹으며 지구 종말 전날 심은 사과-트리로 지구와 화성을 오가며 사과게임을 하는 잡탕 게임이론 문제 구상이 나왔다.
'대회 후기' 카테고리의 다른 글
| KOI 2nd Round Mock 1 (DOJ) 후기 (0) | 2026.06.07 |
|---|---|
| 2024 ICPC Seoul Regional First Round (제22회 KHU 가을 프로그래밍 경시대회) 후기 (0) | 2024.11.09 |
| 월간 향유회 2024. 08. 후기 (4) | 2024.09.02 |
| 2024 신촌지역 대학생 프로그래밍 동아리 연합 여름 대회 (SUAPC 2024 Summer) Open Contest 후기 (3) | 2024.09.02 |
| 삼성전자 제10회 대학생 프로그래밍 경진대회(SCPC) 본선 후기 (16) | 2024.09.02 |
