닉네임 SevenAndHalf로 참가했다. 닉네임의 유래는 우리 학교에 다니는 의문의 학생의 미적분학1 중간고사 점수이다. 정말 충격적이게도 재수강의 결과라고 한다..
결과는 49명 중 18위을 기록했다. 대회 종료 이후 solved.ac에 기여된 난이도를 보면 내가 푼 F까지가 플래티넘이었고, 이후로는 다이아몬드 문제들이었다. 문제 퀄리티도 굉장히 좋았고, 내가 잘푸는 유형의 문제들이 많이 출제되었다. 그래서인지 플래티넘 이하 문제들을 모두 풀었기 때문에 꽤 좋은 퍼포먼스가 나왔다고 생각하는데 등수가 생각보다 낮다. 참가자들의 수준이 그만큼 높았기 때문이라고 믿는다. 이 정도 난이도의 오프라인 대회는 처음이라 살짝 긴장되기도 했다. 하필 옆자리가 1위분이어서 풍선이 늘어나는 걸 보고 벙쪘던 기억도 난다. 그래도 인터넷에서만 보던 고수들의 퍼포먼스를 현장에서 보니 동경의 마음도 들었고 동기부여도 되었다. 앞으로 오프라인 대회에 자주 참여하는 것이 좋을 것 같다.
아무리 패널티 없는 대회라지만 틀린 제출 횟수가 너무 많았던 것 같다. 팀으로 나가는 대회는 대부분 패널티가 있기 때문에 구현의 정확도를 늘리는 연습이 필요할 것 같다.
A번
기본적인 DP 문제다. 풀이는 보자마자 나왔는데 긴장해서 그런지 DP값을 미리 계산해 놓는 기본적인 테크닉을 잊어버리는 실수를 하고 3번 만에 맞았다. 틀린 제출에 대한 패널티가 없는 대회였기 때문에 제출에 대한 부담이 없었지만 저걸 생각하는데 4분이나 걸린 건 문제가 있다고 생각한다.
DP 상태값 3개를 정의하면 풀이는 쉽게 나온다.
$DP_0 :=$ 현재 칸이 빈칸인 경우의 수
$DP_1 :=$ 현재 칸이 속한 그룹의 왼쪽이 비어 있는 경우의 수
$DP_2 :=$ 현재 칸이 속한 그룹의 왼쪽이 막혀 있는 경우의 수
점화식은 코드를 참고하자. 답은 마지막 그룹이 막히면 안되므로 $DP_0[N]+DP_1[N]$이 될 것이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
init();
vector<array<ll, 3>> dp(1000001);
dp[1][0] = 1;
dp[1][2] = 2;
for (ll i = 2; i <= 1000000; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][1] + 2 * dp[i - 1][0]) % MOD;
dp[i][2] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
}
ll t;
cin >> t;
for (ll n; t--; cout << '\n') {
cin >> n;
cout << (dp[n][0] + dp[n][1]) % MOD;
}
return 0;
}
B번
지워진 수들을 모두$1$ 또는 $M$으로 복원하는 것이 최댓값임이 자명하다. 따라서 1을 몇 개 넣을 것인지 순회하면서 최댓값을 구해 주면 정답을 쉽게 얻을 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
init();
ll n, m;
cin >> n >> m;
vector<ll> a(n), v;
ll s = 0, cnt = 0;
for (auto& x : a) {
cin >> x;
s += x;
if (x == 0) cnt++;
else v.emplace_back(x);
}
sort(v.begin(), v.end());
ll b = 0;
for (ll i = 0; i < v.size(); i++) {
b += (2 * i - v.size() + 1) * v[i];
}
ll ans = 0;
for (ll i = 0; i <= cnt; i++) {
ll tmp = b;
tmp += (s - (n - cnt)) * (cnt - i);
tmp += (m * (n - i) - (s + (cnt - i))) * i;
ans = max(ans, tmp);
}
cout << ans;
return 0;
}
C번
이 문제도 4번이나 틀렸던 문제다. 예외 케이스 처리가 많기 때문에 구현이 조금 까다로웠다. 언제 전체적인 안전성이 최대가 될까? 리프 노드가 최소 2개는 있어야 하므로, 선형 트리임이 자명하다. 선형인 트리를 생각했을 때 안전성의 최댓값은 $ N \over 2$이다. 따라서 이 값을 넘는 안전성이 입력으로 들어오는 경우는 불가능하다. 한편, 리프 노드는 최소 2개는 있기 때문에 가장 안전성이 높은 노드를 제외하면 최소 2개씩 필요하다. 최댓값은 $N$이 홀수인 경우와 짝수인 경우를 나눠 처리하면 문제를 해결할 수 있다. 애드혹한 트리의 성질에 대한 이해도를 묻는 문제이기 때문에 개인적으로 골드 수준에서 나올 수 있는 가장 좋은 문제들 중 하나라고 생각한다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
constexpr ll MOD = 1e9 + 7;
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
init();
ll n;
cin >> n;
vector<ll> ex(n);
vector<pll> a(n);
for (ll i = 0, x; i < n; i++) {
cin >> x;
if (x >= n) {
cout << -1;
return 0;
}
ex[x]++;
a[i] = {x, i + 1};
}
ll cnt = 0;
for (ll i = 0; i < n / 2; i++) {
cnt += ex[i];
if (cnt < 2) {
cout << -1;
return 0;
}
cnt -= 2;
}
if (n & 1) {
cnt += ex[n / 2];
if (cnt < 1) {
cout << -1;
return 0;
}
}
sort(a.begin(), a.end());
for (ll i = 2; i < n; i += 2) {
cout << a[i - 2].second << ' ' << a[i].second << '\n';
}
for (ll i = 3; i < n; i += 2) {
cout << a[i - 2].second << ' ' << a[i].second << '\n';
}
cout << a[n - 1].second << ' ' << a[n - 2].second << '\n';
return 0;
}
D번
굉장히 고전했던 문제이다. D, E, F 중 D가 가장 어려웠다고 생각한다. 1시간 10분 정도를 쓰고 어떻게 맞히긴 했지만 제대로 된 증명은 하지 못했고, 해 구성도 여러 케이스들을 손으로 그려 본 후에야 겨우 구현할 수 있었다. 이런 Proof by AC류의 문제들이 정말 어렵다고 생각한다. 익숙치 않기도 하거니와 이게 맞을 거라는 확신을 갖고 코딩하기가 매우 주저되기 때문이다.
결론은 $N$이 $2^M$꼴일 때만 가능하다. 증명이 궁금했는데 나중에 대략적인 풀이를 공개할 때 증명을 알려주지 않아서 나중에라도 증명을 해보려고 한다. 재귀적으로 체스판같이 수를 분배하면 문제를 해결할 수 있는데.. 솔직히 나도 Proof by AC했기 때문에 정확한 풀이를 작성할 수 없다. 이 문제는 추후에 다시 작성할 것이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
init();
ll n;
cin >> n;
if (n == 1) {
cout << "1\n1";
return 0;
}
if (__builtin_popcount(n) != 1) {
cout << 0;
return 0;
}
vector<vector<ll>> ans(n, vector<ll>(n));
function<void(ll, ll, ll, ll, ll)> cal = [&](ll sz, ll x, ll y, ll val, ll cnt) {
if (sz == 1) {
ans[x][y] = val;
return;
}
sz >>= 1;
cal(sz, x, y, val, cnt + 1);
cal(sz, x + sz, y, val + (1 << cnt), cnt + 1);
cal(sz, x, y + sz, val + (1 << cnt), cnt + 1);
cal(sz, x + sz, y + sz, val, cnt + 1);
};
cal(n, 0, 0, 1, 0);
cout << "1\n";
for (auto& v : ans) {
for (auto& x : v) {
cout << x << ' ';
}
cout << '\n';
}
return 0;
}
E번
아직도 뭔지 모르겠는 요상한 값을 계산하는 바람에 조금 말렸던 문제이다. 다시 보니 이날 실수한 것이 굉장히 많다. 실수를 줄이는 연습이 필요함을 다시 느낀다. 하나의 관찰을 했다면 풀이는 간단하다.
우선 경로가 유일해야 하기 때문에 Minimum Spanning Arborescence에서 1이 아닌 어떤 정점 $u$로 들어오는 간선은 최대 1개이다. 따라서 DAG에서 $u$로 들어오는 간선들의 가중치 최솟값의 기댓값을 계산하면 된다. $u$로 들어오는 간선 개수를 $i$라 하자. 이때, 가중치 최솟값이 $j$일 때의 확률을 계산하면 $(j^i-(j-1)^i)/(K^i)$이다. 따라서 기댓값을 계산하면 $\sum^{K}_{j = 1}{K \cdot (j^i-(j-1)^i)/(K^i)} = \sum^{K}_{j = 1}{{j^i}\over{K^i}}$으로 정리된다.
원래 여기서 그냥 나이브하게 계산하는 바람에 시간초과가 발생해 부분점수만 받았다. 이때 시간제한이 5초인 것을 발견해 등장한 $i$들에 대해서만 계산하는 풀이를 증명 없이 믿음의 제출을 했는데 맞았다. 시간복잡도는 정답을 받은 후에 생각해보니 어렵지 않게 증명할 수 있었다. 가능한 $i$값 개수를 생각해 보자. 아무리 많은 서로다른 $i$들이 가능해도 이들의 합은 최대 $M$이므로 $O(K\sqrt{M}log(MOD))$에 모두 계산해둘 수 있다. 이제 2부터 N까지 모든 정점들의 기댓값을 더하면 정답을 얻을 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
constexpr ll MOD = 998244353;
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll power(ll n, ll k) {
ll ret = 1;
while (k) {
if (k & 1) (ret *= n) %= MOD;
(n *= n) %= MOD;
k >>= 1;
}
return ret;
}
int main() {
init();
ll n, m, k, ans = 0;
cin >> n >> m >> k;
vector<ll> cnt(n + 1);
vector<bool> vst(m + 1);
for (ll u, v, i = 0; i < m; i++) {
cin >> u >> v;
cnt[v]++;
}
for (ll i = 2; i <= n; i++) {
vst[cnt[i]] = true;
}
vector<ll> s(m + 1);
for (ll i = 1; i <= m; i++) {
if (!vst[i]) continue;
for (ll j = 1; j <= k; j++) {
(s[i] += power(j, i)) %= MOD;
}
s[i] *= power(power(k, i), MOD - 2);
}
for (ll i = 2; i <= n; i++) {
(ans += s[cnt[i]]) %= MOD;
}
cout << ans;
return 0;
}
F번
티어는 가장 높지만 쉽다고 느꼈던 문제였다. 처음에는 기하학 문제라고 생각했는데, 나는 기하학에 대한 숙련도가 많이 부족했기 때문에 지레 겁을 먹었지만 기하학 문제가 아니었다. 예제도 친절한 편이어서 몇 번 그림을 그려 보니 정답을 유추할 수 있었다.
안쪽에 있는 정점 하나를 정하자. 이 정점 외부는 볼록 껍질로 둘러져 있어야 한다. 이 정점과 하나를 제외한 외곽 정점들 사이에 파란 간선을 연결하고 하나는 빨간 정점을 연결한다. 반대로, 각도정렬한 상태의 외곽 정점들을 하나 빼고 모두 빨간 간선을, 하나를 파란 간선을 연결하면 정답이 구성된다. 한편, 모든 정점이 하나의 볼록 껍질에 속하면 겹치지 않고 그을 수 있는 간선의 수가 $2N$이 안되기 때문에 불가능하다.
볼록 껍질 혹은 각도 정렬을 통해 구현할 수 있다. 팀노트도 안가져갔고 볼록 껍질 코드도 짤 줄 몰랐기 때문에 나는 atan함수를 이용해서 모든 정점을 기준으로 각도정렬을 시도하는 방법으로 해결하였다. 심지어 atan2 함수도 몰라서 atan함수로 일일이 경우를 나눠서 각도 정렬을 했다... 다행히 채점기를 편하게 만들기 위함인지 $N$의 크기가 작아서 풀 수 있었다. 문자열이나 기하 알고리즘을 잘 모르는 편인데 내가 재미 없다고 대회에 나오지 않는 것이 아니니까 숙련도를 쌓아야할 필요성을 느꼈다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
constexpr ll MOD = 998244353;
const ld PI = acos(-1);
inline void init() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main() {
init();
ll n;
cin >> n;
vector<pll> d(n);
vector<ll> tmp;
for (auto& [x, y] : d) cin >> x >> y;
ll r = -1;
for (ll i = 0; i < n; i++) {
vector<pair<ld, ll>> v;
auto [x, y] = d[i];
for (ll j = 0; j < n; j++) {
if (i == j) continue;
auto [nx, ny] = d[j];
ll dx = nx - x, dy = ny - y;
if (dx == 0) {
v.emplace_back(dy > 0 ? PI * 0.5 : PI * 1.5, j);
} else {
ld t = atan(ld(dy) / ld(dx));
if (t < 0) {
if (dx > 0) {
t += 2 * PI;
} else {
t += PI;
}
} else {
if (dx < 0) {
t += PI;
}
}
v.emplace_back(t, j);
}
}
sort(v.begin(), v.end());
ll sz = v.size();
v.emplace_back(v[0].first + 2 * PI, v[0].first);
bool imp = false;
for (ll j = 1; j < v.size(); j++) {
if (v[j].first - v[j - 1].first >= PI) {
imp = true;
break;
}
}
if (imp) continue;
r = i;
for (ll j = 0; j < sz; j++) {
tmp.emplace_back(v[j].second);
}
break;
}
if (r == -1) {
cout << -1;
return 0;
}
cout << 2 * n - 2 << '\n';
for (ll i = 0; i < n; i++) {
if (i == r or i == tmp[0]) continue;
cout << r + 1 << ' ' << i + 1 << " R\n";
}
cout << tmp[0] + 1 << ' ' << tmp.back() + 1 << " R\n";
cout << r + 1 << ' ' << tmp[0] + 1 << " B\n";
for (ll i = 1; i < tmp.size(); i++) {
cout << tmp[i - 1] + 1 << ' ' << tmp[i] + 1 << " B\n";
}
return 0;
}'대회 후기' 카테고리의 다른 글
| 2025 ICPC Seoul Regional 본선 후기 (2) | 2025.11.26 |
|---|---|
| 2025 숭고한 연합 알고리즘 경진대회 후기 (2) | 2025.09.02 |
| SCPC 2025 본선 후기 (0) | 2025.09.02 |
| SCPC 2025 2차 예선 후기 (0) | 2025.09.01 |
| SCPC 2025 1차 예선 후기 (0) | 2025.09.01 |
