대회장에 처음 들어갔을 때, PS 대회 중 이렇게 품격있는 광경은 처음이라 놀랐던 기억이 난다. 역시 우리나라 최대의 기업이라 그런지 마우스, 키보드, 장패드 등의 기념품도 쏠쏠하게 챙겨주었다. 진행자로 현직 아나운서 분을 모신 것을 보고 대기업은 다르다는 생각이 들었다. 한 가지 아쉬운 점은 5등상이 사라졌다는 것인데 상금 소멤 필요 없으니까 상장만이라도 주면 좋겠다..
대회 시작 전에 환경을 세팅하는 시간이 있었는데 VSCode를 사용하려 했지만 시간이 촉박해서 제대로 설정을 못했다. 내가 평소 쓰는 IDE인 CLion이 지원되지 않았고, 내가 평생 macOS만 써왔다 보니 윈도우 환경에 익숙하지 않은 점도 크게 작용한 것 같다. 키보드도 익숙하지 않아서 코딩하는 데 불편한 환경이었던 건 사실이나, 내가 쓴 시간 중 코딩에 쓴 시간은 많지 않아서 익숙한 환경이었어도 결과는 똑같지 않았을까.. 그래도 다음에는 이를 반면교사 삼아서 미리 대회 환경에 익숙해지도록 노력해야겠다.
1, 2번 문제를 해결하고 5번 부분점수를 받았지만 수상은 하지 못했다. 2번까지 빠르게 해결한 후 다른 문제들의 부분점수를 받았어야 승산이 있었을 것 같지만 2번까지 푸는 데 너무 많은 시간을 써버렸다. 1번은 빠르게 해결해서 여기까지는 순조롭다고 생각했다. 2번 문제가 내가 나름 자신있는 구성적 문제여서 바로 도전했지만 첫 솔브가 빨리 나온 것 치고 문제의 해법의 갈피를 잡는 것 조차 어려웠다. 2번을 버리고 다른 문제를 파는 도박수도 있었겠지만 만점자 수를 보니 엄두가 나지 않아서 계속 2번을 붙잡았고, 장장 3시간만에 해결했다. 2번을 못풀었으면 아쉬운 마음이 훨씬 컸을 것 같은데 3시간이나 걸렸지만 결국 풀어내서 후련한 마음도 든다.
AI가 밥그릇을 뺏어간 여파로 5등상이 사라져서 안그래도 어려웠던 수상이 더 어려워졌기에 큰 기대는 안했지만 막상 대회가 끝나고 나니 아쉬운 결과가 되었다. 그래도 한 학기동안 내가 공부한 것을 모두 쏟아냈다고 생각하기 때문에 후회는 없다. 아직 1학년이기 때문에 기회가 많기도 하고, 5등상이 있었다면 수상을 노려 볼 만했다고 생각하기 때문에 내년에는 4등상을 목표로 다시 도전할 것이다.
1번 풀이
꽤 빠르게 해결했던 노솔 방지용 문제이다. $DP[i][j]$을 $(i, j)$가 막혀 있을 때 얻을 수 있는 최대 이익으로 정의하면 점화식을 쉽게 세울 수 있다. 점화식은 코드로 확인하는 것이 편할 것이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
constexpr ll dx[] = {-2, -2, -2, -1, 0}, dy[] = {0, -1, -2, -2, -2};
void solution() {
ll n, ans = 0;
cin >> n;
vector<vector<ll>> dp(n + 2, vector<ll>(n + 2));
for (ll i = 2; i <= n + 1; i++) {
for (ll x, j = 2; j <= n + 1; j++) {
cin >> x;
for (ll d = 0; d < 5; d++) {
ll pi = i + dx[d], pj = j + dy[d];
dp[i][j] = max(dp[i][j], dp[pi][pj] + x);
}
dp[i][j] = max({dp[i][j], dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
ans = max(ans, dp[i][j]);
}
}
cout << ans;
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';
solution();
cout << '\n';
}
}2번 풀이
내가 가장 힘들었던 문제이다. 처음에는 세그먼트 트리나 분할 정복 과정을 모방해서 구간에 대한 합을 빠르게 계산하려고 했다. 하지만 01이 반복되는 수열의 경우를 절대 해결할 수가 없었다. 그래서 생각한 것이 이 분할 정복 과정을 여러 개 만드는 것이었다. 예를 들어 홀수, 짝수를 분리해서 과정을 처리하던가 혹은 더 많은 경우의 수를 나눠서 여러 개 만드는 것이다. 당연히 될리가 없었지만 대회 후에 들으니 이런 방식으로 푼 사람이 있다고 한다. 아마 데이터가 약해서 뚫리지 않았을까 싶은데 조금은 억울한 부분이다. 시도조차 해보지 않은 것이 잘못이지 않을까 싶다.
분할 정복을 이용한 방법이 아닌 것 같아서 좀 더 다양한 방법들을 고민해도 풀이가 쉽게 떠오르지 않았다. 이 문제를 고민하기 시작한지 2시간 30분 쯤 지나던 중, 갑자기 제곱근 분할법이 떠올랐고, 수열을 분할하는 아이디어가 떠올랐다. 수열을 블록으로 분할해서 블록 내부에서 브루트포스를 통해 모든 합을 관리하고, 각각의 수열은 블록을 합해서 계산하는 방식이었다. 블록 내부의 모든 경우의 수를 만드는 연산 횟수는 블록의 개수 $N \over B$와 블록 내부의 모든 경우의 수$2^B$을 곱해 얻을 수 있다. 이는 비트마스킹을 이용해 간편하게 구현할 수 있다. 이제 합치는 것을 생각하자. 수열 한 번에 블록 개수만큼 값을 더해 줘야 하므로 수열의 개수 $N$과 블록 개수 $N \over B$를 곱하면 연산 횟수를 구할 수 있다. 따라서 총 연산 횟수는 두 값을 더한 ${N {2^B} + {N^2}} \over B$이다.
처음에는 대충 블록 크기를 10으로 설정해서 계산해 봤더니 제한을 살짝 넘었다. 운이 좋은건지 나쁜건지 8로 낮춰서 계산했더니 제한 안에 딱 들어왔다. 8을 제외한 값들은 제한을 넘는다고 들었다. 계산 결과를 처음 확인했을 때만큼은 머릿속에 먹구름이 다 사라지는 기분이었지만, 풀이가 생각보다 너무 어이없어서 허탈하도 했다. 이후 그대로 구현해서 1번에 만점을 받았다. 지금 생각해 보면 왜 분할이 이렇게 늦게 생각났는지 의문이 든다. 앞으로 같은 문제를 다양한 방법으로 풀어 보는 등의 방법을 통해 Local Minima를 빠져나올 수 있는 훈련을 해야 겠다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void solution() {
ll n;
cin >> n;
vector<vector<ll>> a(n, vector<ll>(n));
for (ll i = 0; i < n; i++) {
string s;
cin >> s;
for (ll j = 0; j < n; j++) {
a[i][j] = s[j] - '0';
}
}
vector<pll> q;
vector<ll> t(n);
ll idx[125][1 << 8];
for (ll i = 0; i * 8 < n; i++) {
ll mx = min(8LL, n - i * 8);
for (ll j = 0; j < mx; j++) {
ll b = 8 * i;
idx[i][1 << j] = b + j + 1;
}
for (ll s =1;s < 1 << mx; s++) {
if (__builtin_popcount(s) == 1) continue;
for (ll j = 0; j < mx; j++) {
if (s & 1 << j) {
q.emplace_back(idx[i][1 << j], idx[i][s ^ 1 << j]);
idx[i][s] = q.size() + n;
break;
}
}
}
}
for (ll i = 0; i < n; i++) {
ll p = -1;
for (ll j = 0; j * 8 < n; j++) {
ll mx = min(8LL, n - j * 8);
ll b = j * 8, st = 0;
for (ll k = 0; k < mx; k++) {
st |= a[i][b + k] << k;
}
if (!st) continue;
if (p == -1) {
p = idx[j][st];
} else {
q.emplace_back(p, idx[j][st]);
p = q.size() + n;
}
}
t[i] = p;
}
cout << q.size() << '\n';
for (auto& [x, y] : q) {
cout << x << ' ' << y << '\n';
}
for (auto& x : t) {
cout << x << ' ' ;
}
}
int main() {
init();
ll tc;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';
solution();
cout << '\n';
}
}5번 부분점수
가장 쉬운 부분점수 같아 보여서 빠르게 해결했다. 단순히 백트래킹으로 점수를 얻을 수 있었다. 출력 버퍼 flush를 안해준 것 때문에 여러 번 틀린 것이 아쉬운 점이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void solution() {
ll n, m;
cin >> n >> m;
vector<vector<ll>> gr(n + 1);
for (ll u, v, i = 0; i < m; i++) {
cin >> u >> v;
gr[u].emplace_back(v);
}
vector<ll> ans, c;
vector<bool> vst(n + 1);
function<void(ll)> dfs = [&](ll cur) {
if (ans.size() == n) return;
if (ans.size() < c.size()) ans = c;
for (auto& nxt : gr[cur]) {
if (vst[nxt]) continue;
c.emplace_back(nxt);
vst[nxt] = true;
dfs(nxt);
if (ans.size() == n) return;
vst[nxt] = false;
c.pop_back();
}
};
for (ll s = 1; s <= n; s++) {
vst[s] = true;
c.emplace_back(s);
dfs(s);
vst[s] = false;
c.pop_back();
}
cout << ans.size() - 1 << '\n';
for (auto& x : ans) cout << x << ' ';
}
int main() {
init();
ll tc = 0;
cin >> tc;
for (ll t = 1; t <= tc; t++) {
cout << "Case #" << t << '\n';
solution();
cout << endl;
}
}
'대회 후기' 카테고리의 다른 글
| 2025 ICPC Seoul Regional 본선 후기 (2) | 2025.11.26 |
|---|---|
| 2025 숭고한 연합 알고리즘 경진대회 후기 (2) | 2025.09.02 |
| SCPC 2025 2차 예선 후기 (0) | 2025.09.01 |
| SCPC 2025 1차 예선 후기 (0) | 2025.09.01 |
| 2025 KAIST RUN Spring Contest 후기 (0) | 2025.05.31 |
