7월 29일
주로 모의고사 중심으로 진행되었으며, 일부 문제에 대한 분석과 후기 포함.
T1
간단한 시뮬레이션 문제. CSP-S2023 T3보다도 쉬웠다. 디버그 문구를 지우지 않아서 실수했지만, 다행히 오답은 아니었다. 복잡도가 높을 수 있다는 점을 인지하고, 더 효율적인 접근 방식을 고려해야 한다. 결국 코드는 통과했으나, 조건이 애매하면 예외 처리가 필요하다.
T2
초기에는 미스터리한 특수 알고리즘(Ad-hoc)으로 착각했지만, 실제로는 0-1 배낭 문제였다. 상태를 dp[i][h][g][e]로 정의해, 전략적으로 이전 단계에서 남은 인원수 h, 석유량 g, 제품 수 e에 따라 최대 전력량을 갱신하면 된다. 다만 p가 최대 10⁴까지 가능해, 전체 시간/공간 복잡도가 불리하다. 이를 해결하기 위해 전력량과 제품 수의 상태를 바꿔 dp[i][h][g][p]로 재정의하면, 최종 답을 구할 때 전력량이 유효한지 확인하고, 제품 수의 최댓값을 취하면 된다. 또한, 상한선을 너무 높게 설정하면 상수 최적화에서 문제가 발생하므로, 변화량이 10 이내라는 점을 활용해 제한을 조절해야 한다.
코드 보기
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=114514, M=1919810;
ll n, m, hs, subid, dp[45][15][405][405];
struct Task {
ll h, g, p, e;
} a[N];
int main() {
freopen("grid.in", "r", stdin);
freopen("grid.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> hs >> subid;
for (int i = 1; i <= n; ++i)
cin >> a[i].h >> a[i].p >> a[i].g >> a[i].e;
memset(dp, -0x3f, sizeof(dp));
for (int i = 1; i <= n; ++i)
if (a[i].g >= 0 && a[i].p >= 0 && a[i].e >= 0 && hs + a[i].h >= 0)
dp[1][hs + a[i].h][a[i].g][a[i].e] = max(dp[1][hs + a[i].h][a[i].g][a[i].e], a[i].p);
for (int i = 2; i <= m; ++i)
for (int j = 1; j <= n; ++j)
for (int h = 0; h <= hs; ++h)
for (int g = 0; g <= i * 10; ++g)
for (int e = 0; e <= i * 10; ++e)
if (h >= a[j].h && h - a[j].h <= hs &&
g >= a[j].g && g - a[j].g <= 400 &&
e >= a[j].e && e - a[j].e <= 400 &&
dp[i-1][h - a[j].h][g - a[j].g][e - a[j].e] + a[j].p >= 0)
dp[i][h][g][e] = max(dp[i][h][g][e],
dp[i-1][h - a[j].h][g - a[j].g][e - a[j].e] + a[j].p);
ll ans = 0;
for (int i = 1; i <= m; ++i)
for (int h = 0; h <= hs; ++h)
for (int g = 0; g <= 400; ++g)
for (int e = 0; e <= 400; ++e)
if (dp[i][h][g][e] >= 0)
ans = max(ans, e);
cout << ans;
return 0;
}
T3
피타고라스 정리 형태의 방정식: $a_l x_l + \cdots + a_r x_r = v$ 의 양의 정수 해 개수. 이는 최대공약수 $\gcd(a_l, \dots, a_r)$ 의 배수만 표현 가능하다는 성질을 이용하면, 해의 수는 $\left\lfloor \frac{v}{\gcd} \right\rfloor$ 가 된다. 수정 연산은 선분 트리로 관리하면 되며, 간단한 구현이다. 내가 못 푼 이유는 음수 해도 가능하다는 점을 간과했기 때문이다.
T4
난이도는 낮았지만, 시간 부족으로 미완성. 이후 보완 예정.
결론: 기본 실수 없이 140점, 생각을 조금 더 하면 240점, 아이디어가 있으면 340점. 나는 여전히 무능하다.
또한, 이곳에 온 동료들 중 일부는 내가 알고 있는 사람들이라는 사실을 알게 되었는데, 그들의 소속 학교는 아직 모르겠다.
7월 30일
하루 종일 강의만 듣고, 문제 풀이 시간이 거의 없었다. 내일 보충 예정. 동적 프로그래밍과 그래프 이론을 다뤘으며, 그래프 부분에서 의미 있는 내용을 습득했다. 저녁엔 동적 프로그래밍 문제에 매달렸다.
7월 31일
더 이상의 진전이 없음. 난이도가 올라가면서 모든 문제에 대한 접근이 어려워졌다. 특히 T2에서 아이디어를 어떻게 구현할지 몰라 막혔다. 혹시 아이디어 자체가 잘못된 것인지, 아니면 시간이 부족해서 다른 문제에 집중하지 못했는지 모른다.
T1은 이차 등차수열을 유도하여 공식을 찾았다: $$ \sum_{i=1}^n (2i+1)(2i+3) = \frac{n(n+1)(n+2)}{6} + \frac{n(n+1)}{2} + 3 $$
T2는 중위값 기반 이진 탐색으로 접근. 각 값 $v_i$를 기준으로 왼쪽과 오른쪽의 가격을 저장하는 두 개의 가중치 세그먼트 트리를 사용. 이진 탐색으로 가능한 최대 물품 수를 찾고, 총 비용이 예산 내에 들면 업데이트. 마지막으로 후순위 최댓값으로 정리.
코드 보기
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls now<<1
#define rs now<<1|1
const ll N=1000005, M=1919810, mod=998244353;
struct ValTree {
ll sum[4*N], num[4*N];
void update(ll now, ll l, ll r, ll x, ll k) {
sum[now] += x * k;
num[now] += k;
if (l == r) return;
ll mid = (l + r) >> 1;
if (x <= mid) update(ls, l, mid, x, k);
else update(rs, mid+1, r, x, k);
}
ll query(ll now, ll l, ll r, ll x) {
if (sum[now] < x) return mod;
if (l == r) return l * x;
ll mid = (l + r) >> 1;
if (x <= num[ls]) return query(ls, l, mid, x);
return query(rs, mid+1, r, x - num[ls]) + sum[ls];
}
} t1, t2;
ll n, m, T, ans[N];
struct Item {
ll w, v;
} a[N];
bool cmp(Item x, Item y) {
return x.v != y.v ? x.v < y.v : x.w < y.w;
}
bool check(ll i, ll mid) {
return (t1.query(1, 1, 1e6, mid) + t2.query(1, 1, 1e6, mid) + a[i].w <= m);
}
int main() {
freopen("gift.in", "r", stdin);
freopen("gift.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> T;
ans[n+1] = -1;
for (int i = 1; i <= n; ++i) cin >> a[i].v >> a[i].w, ans[i] = -1;
sort(a+1, a+n+1, cmp);
for (int i = 2; i <= n; ++i) t2.update(1, 1, 1e6, a[i].w, 1);
for (int i = 1; i <= n; ++i) {
ll l = 0, r = min(i-1LL, n-i), res = 0;
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(i, mid)) l = mid + 1, res = mid;
else r = mid - 1;
}
ans[res] = a[i].v;
if (i != n) {
t2.update(1, 1, 1e6, a[i+1].w, -1);
t1.update(1, 1, 1e6, a[i].w, 1);
}
}
for (int i = n; i >= 1; --i) ans[i] = max(ans[i], ans[i+1]);
while (T--) {
ll q; cin >> q;
cout << ans[q/2] << '\n';
}
return 0;
}
T3은 $O(n^2)$ DP부터 시작해, 구간 확장 시 특정 원소의 등장 횟수가 변하는 특성을 이용. 같은 값의 위치를 추적하여 구간에 대해 +1 또는 -1 연산을 수행하고, 분할 정복으로 관리. 각 블록마다 누적합과 범위 조건을 저장해, 특정 조건을 만족하는 위치의 합을 빠르게 계산.
코드 보기
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define lxl long long
const ll N=114514, M=1919810, B=401;
const lxl mod=1e9+7;
ll n, p, a[N], ns, nq, st[N], ed[N], bel[N];
ll las[N], bu[N];
lxl dp[N], sum[B][N], pr[B], tag[B], cnt[N];
void pushdown(ll id) {
for (int i = st[id]; i <= ed[id]; ++i)
sum[id][cnt[i]] = 0, cnt[i] += tag[id];
tag[id] = pr[id] = 0;
}
void update(ll id) {
for (int i = st[id]; i <= ed[id]; ++i) {
sum[id][cnt[i]] = (sum[id][cnt[i]] + dp[i-1]) % mod;
if (cnt[i] <= p) pr[id] = (pr[id] + dp[i-1]) % mod;
}
}
void modify(ll l, ll r, ll k) {
ll lx = bel[l], rx = bel[r];
if (lx == rx) {
pushdown(lx);
for (int i = l; i <= r; ++i) cnt[i] += k;
update(lx); return;
}
pushdown(lx), pushdown(rx);
for (int i = l; i <= ed[lx]; ++i) cnt[i] += k;
for (int i = st[rx]; i <= r; ++i) cnt[i] += k;
update(lx), update(rx);
for (int i = lx+1; i < rx; ++i) {
if (k == 1) {
pr[i] -= sum[i][p - tag[i]];
tag[i]++;
} else {
tag[i]--;
pr[i] += sum[i][p - tag[i]];
}
}
}
lxl query(ll l, ll r) {
lxl ans = 0;
ll lx = bel[l], rx = bel[r];
if (lx == rx) {
pushdown(lx), update(lx);
for (int i = l; i <= r; ++i)
if (cnt[i] <= p) ans = (ans + dp[i-1]) % mod;
return ans;
}
pushdown(lx), update(lx);
pushdown(rx), update(rx);
for (int i = l; i <= ed[lx]; ++i) if (cnt[i] <= p) ans = (ans + dp[i-1]) % mod;
for (int i = st[rx]; i <= r; ++i) if (cnt[i] <= p) ans = (ans + dp[i-1]) % mod;
for (int i = lx+1; i < rx; ++i) ans = (ans + pr[i]) % mod;
return ans;
}
int main() {
freopen("home.in", "r", stdin);
freopen("home.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> p; ++n;
ns = sqrt(n), nq = ceil(n * 1.0 / ns);
for (int i = 1; i <= nq; ++i) {
st[i] = ns*(i-1)+1, ed[i] = min(ns*i, n);
for (int j = st[i]; j <= ed[i]; ++j) bel[j] = i;
}
for (int i = 2; i <= n; ++i) {
cin >> a[i];
las[i] = max(bu[a[i]], 1);
bu[a[i]] = i;
}
dp[1] = 1;
modify(1, 1, 1);
update(bel[1]);
for (int i = 2; i <= n; ++i) {
ll l = las[las[i]], r = i;
if (las[i] != 1) modify(l+1, las[i], -1);
modify(las[i]+1, r, 1);
dp[i] = query(1, r);
}
cout << (dp[n] % mod + mod) % mod;
return 0;
}
T4는 원래 문제였고, 매우 어렵다. 많은 사람이 퇴장하거나 게임을 즐기며 시간을 보내는 모습을 보여줬다. 아무리 잘해도 이미 결말이 정해져 있다. 이제는 본인의 실력을 인정하고, NOIP 준비에 집중하자.
8월 1일
오전: 문자열 강의. 교수님은 형식적인 설명만 하며, 이해가 안 됐다. 자동기 기반 설명이라, 대부분이 혼란스러워했다. 오전 수업의 유일한 수확은 『룡계Ⅱ』를 완독한 것. 오히려 모의고사 한 번 더 하는 것이 나았을 정도.
오후: 그리디 알고리즘. 비교적 좋았지만, 수업 후반부에도 관심이 줄어들었다. 그리디는 직관적이지 않기 때문에, 문제를 많이 풀어야 한다.
저녁: 문자열 관련 문제를 풀었지만, 시간이 부족함을 느꼈다. 매번 늦게 끝나는 느낌. 마찬가지로, 매너링이나 Z함수는 아직 공부하지 않았다. 해시에 의존하게 되는 경향이 있다.
8월 2일
현재까지의 결과는 매우 불안정.
T1: 메모이제이션을 사용. 현재 총 횟수, 보상 획득 횟수, 스타하트 보유량을 상태로 삼아 확률 기반 탐색. 하지만 코드 길이와 로직 복잡도로 인해 오류 가능성 존재.
코드 보기
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define db double
const ll N=100005, M=1919810;
const db b3=40.0/98.0, b4=50.0/98.0, b5=8.0/98.0;
const db eps=1e-9;
ll nx;
db ans[405][105][305];
ll get(ll x) {
if(x < 10) return 0;
if(x < 28) return 1;
if(x < 68) return 3;
if(x < 138) return 8;
if(x < 258) return 18;
return 38;
}
db dfs(ll dep, ll x, ll y) {
if (ans[dep][x][y]) return ans[dep][x][y];
ll tot = nx + get(y);
if (tot < dep) return 0;
db res = 0;
db p6 = 0.02 + 0.02 * max(x - 50, 0);
db p5 = (1.0 - p6) * b5, p4 = (1.0 - p6) * b4, p3 = (1.0 - p6) * b3;
if (p3 > eps) res += p3 * dfs(dep + 1, x + 1, y);
if (p4 > eps) res += p4 * dfs(dep + 1, x + 1, min(y + 1, 258));
if (p5 > eps) res += p5 * dfs(dep + 1, x + 1, min(y + 6, 258));
res += p6 * 0.65 * dfs(dep + 1, 1, min(y + 10, 258));
res += p6 * 0.35;
ans[dep][x][y] = res;
return res;
}
int main() {
freopen("allin.in", "r", stdin);
freopen("allin.out", "w", stdout);
cin >> nx;
printf("%.6f", dfs(1, 1, 0));
return 0;
}
T2: DP 문제지만, 실수로 미완성.
T3: 임의 선택(randomization)으로 해결. 작은 인덱스/큰 인덱스의 간선을 직접 탐색하고, 중간은 무작위로 연결. 시간 복잡도는 $O(B^2 + n^2/B)$, $B = n^{2/3}$ 시 최적.
T4: 해시로 30점만 획득. 정답은 복잡하고, 자신감이 무너짐.
8월 3일
자신감 상실. 훈련량, 실력, 시간 모두 부족. 이제는 NOIP 그룹에서 평범하게 살아가는 것이 현실이다.
언제부터인지, 동료들과의 대화에서 제외됨. 스스로를 ‘폐물’로 인식하면, 자기 하한선은 깊어진다.
하지만… 정말 또 한 번만 더, 연습회 1등을 하고 싶다. 그러나 지금의 실력으로는 불가능하다.
결국, 훈련을 포기하고, 휴식을 취하며 삶을 정리해야 할 시점이다.
8월 4일
모든 문제를 해결하지 못했고, 경기 참가도 포기. 첫 주 훈련 종료.
8월 5~10일
기록을 늦게 작성한 탓에, 일부 내용이 누락됨.
8월 6일: NOIP 모의고사 1회, 랭킹 28. 실력이 여기까지다.
- T1: 이분탐색 + 비트마스크 DP → 미숙
- T2: 지능형 카운팅 → 이해 불가
- T3: 트리 분할 → 기본 문제
- T4: 데이터 구조 → 손도 못 댐
T1과 T4에서 10점씩 떨어졌지만, 20점 추가로 랭킹 19. 실력은 이 정도다.
8월 7일
T1: 이분탐색 + BFS → 코드 길고 실수 많음. T2: 특수 DP → 이해 불가. T3: 지능형 그리디 → 실력 부족. T4: CF*3500 수준의 데이터 구조 → 도저히 안 됨. 비록 16점은 얻을 수 있었지만, T1에서 시간을 너무 많이 썼다.
8월 9일
GCX와 함께 팀으로 경기. 랭킹 1. 하지만 난이도는 가장 낮은 편. T1: 간단한 수학. T2: 흥미로운 개념. T3: 구간 DP → 데이터가 너무 약해, O(n) 그리디로 90점도 가능. T4: 차분 → 시간 부족.
최선의 전략은 T1, T2, T4를 빠르게 해결하고, T3는 브루트포스로.
"이 랭킹 1은 어떤 학교에서 나왔나요?" (‘사립상반대중학교’라고 적었는데, 사람들은 당황함)
저녁엔 『룡계4』 읽으며 휴식.
8월 10일
훈련 종료. 정리할 마음이 없다.