1학년때 PS를 쉬었던 탓에 SCPC를 올해 처음으로 참가해본다. 그래서 1차 예선때도 버퍼 플러시 이슈로 만점을 받지 못해 조금 안타까웠다.
VDI 환경도 생소하여 이전 참가자 분들에게 대충 전해들은 정도로만 알고 있었는데 충격적이게도 본선 관련 메일에 맥 OS는 보안문제로 프로그램을 실행하지 못한다는 안내가 와있었다.... (진짜 애플은 국제적 왕따인가? 왜 세상 만사 다 맥에서는 안돌아가지?) 다시한번 다음 노트북은 윈도우를 사용하겠다는 의지가 샘솟고 하고 또 맥북을 얻게된다면 그냥 내다 팔아야겠다는 다짐을 하게 되었다. 덕분에 에어컨 없는 옆방에서 데스크톱을 쓰느라 덥고 키입력도 어색했지만 대회에 큰 지장은 없었다.
1번 시간 여행 - 100/100 - 20분
문제가 정확히는 기억나지 않지만 대충 정렬하고 투포인터로 풀었다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int res, inf = 1000000;
struct segtree {
vector<int> tree;
void init() {
tree.resize(res, inf);
}
void update(int t1, int t2, int q, int val, int idx) {
if (q < t1 || t2 < q) return;
if (t1 == t2) {
if (val == 1) tree[idx] = t1;
else tree[idx] = inf;
return;
}
int mid = (t1 + t2) / 2;
update(t1, mid, q, val, idx * 2);
update(mid + 1, t2, q, val, idx * 2 + 1);
tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
}
int query(int t1, int t2, int q1, int q2, int idx) {
if (q2 < t1 || t2 < q1) return inf;
if (q1 <= t1 && t2 <= q2) return tree[idx];
int mid = (t1 + t2) / 2;
return min(query(t1, mid, q1, q2, idx << 1), query(mid + 1, t2, q1, q2, (idx << 1) | 1));
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N, K;
cin >> N >> K;
res = 1;
while (res < (N << 1)) {
res <<= 1;
}
segtree tree;
tree.init();
long long ans = 0;
vector<pair<int, int>> ttrav(N);
for (int i = 0; i < N; i++) {
cin >> ttrav[i].first;
ttrav[i].second = i;
}
sort(ttrav.begin(), ttrav.end());
queue<pair<int, int>> que;
for (pair<int, int> i : ttrav) {
while (que.size() && que.front().first + K < i.first) {
pair<int, int> tmp = que.front();
que.pop();
tree.update(0, N - 1, tmp.second, -1, 1);
}
ans += max(0, i.second - tree.query(0, N - 1, 0, i.second - 1, 1));
tree.update(0, N - 1, i.second, 1, 1);
que.push(i);
}
cout << "Case #" << t << '\n' << ans << '\n';
}
return 0;
}
2번 공장 - 200/200 - 1시간 57분
대회가 끝다고 ICPC 팀원인 penguin1234 님의 풀이를 들어보니 정해는 sparse table에 DAG의 원리를 접목해서 어쩌고 하는것 같았다. 나는 희소 배열을 사용해도 쿼리마다 O(Ri^2 * logN)이 걸리는 풀이밖에 생각나지 않아 대회에서는 처음으로 루트질을 사용해 보았다. 전체 테스트케이스의 구간 입력값의 개수에 대해 Ri가 루트개 이하인 경우는 희소 배열을 사용했고 그렇지 않은 경우는 O(N) dp로 답을 구했다. O(NsqrtN)을 살짝 넘는 풀이인데 예선과 다르게 전체 입력에서의 N의 합이 주어져서 걱정이 되었지만 다행이 통과되었다. 만점자 수를 보았을때 상당히 빨리 2번까지 풀었다는것을 알아서 이때까지는 기분이 좋았다...
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N, totedgesum;
cin >> N;
totedgesum = N;
vector<pair<int, int>> nst(N);
vector<int> xs;
for (pair<int, int>& i : nst) {
cin >> i.first >> i.second;
xs.push_back(i.first);
xs.push_back(--i.second);
}
int Q;
cin >> Q;
vector<vector<pair<int, int>>> query(Q);
for (vector<pair<int, int>>& i : query) {
int Ri;
cin >> Ri;
i.resize(Ri);
totedgesum += Ri;
for (pair<int, int>& j : i) {
cin >> j.first >> j.second;
xs.push_back(j.first);
xs.push_back(--j.second);
}
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
vector<int> edge(xs.size(), -1);
int res = 0;
while ((1 << res) <= xs.size()) {
res++;
}
vector<vector<int>> sptable(res, vector<int>(xs.size(), -1));
for (pair<int, int>& i : nst) {
i.first = lower_bound(xs.begin(), xs.end(), i.first) - xs.begin();
i.second = lower_bound(xs.begin(), xs.end(), i.second) - xs.begin();
if (edge[i.second] == -1 || edge[i.second] < i.first) edge[i.second] = i.first;
if (sptable[0][i.first] == -1 || sptable[0][i.first] > i.second) {
sptable[0][i.first] = i.second;
}
}
for (int i = xs.size() - 2; i >= 0; i--) {
if (sptable[0][i] == -1 || sptable[0][i + 1] < sptable[0][i]) {
if (sptable[0][i + 1] != -1) sptable[0][i] = sptable[0][i + 1];
}
}
for (int i = 1; i < res; i++) {
for (int j = 0; j < xs.size(); j++) {
int sptmp = sptable[i - 1][j];
if (sptmp == -1 || sptmp + 1 == xs.size()) continue;
int sptmp2 = sptable[i - 1][sptmp + 1];
sptable[i][j] = sptmp2;
}
}
vector<int> qfidx(xs.size());
cout << "Case #" << t << '\n';
for (vector<pair<int, int>> q : query) {
long long qsize = q.size();
if (qsize * qsize >= totedgesum) {
vector<int> qedge(xs.size(), -1);
for (pair<int, int> i : q) {
i.first = lower_bound(xs.begin(), xs.end(), i.first) - xs.begin();
i.second = lower_bound(xs.begin(), xs.end(), i.second) - xs.begin();
if (qedge[i.second] == -1 || qedge[i.second] < i.first) qedge[i.second] = i.first;
}
vector<int> qmafront(xs.size());
for (int i = 0; i < xs.size(); i++) {
if (i) qmafront[i] = qmafront[i - 1];
if (edge[i] != -1) {
if (edge[i]) qmafront[i] = max(qmafront[i], qmafront[edge[i] - 1] + 1);
else qmafront[i] = max(qmafront[i], 1);
}
if (qedge[i] != -1) {
if (qedge[i]) qmafront[i] = max(qmafront[i], qmafront[qedge[i] - 1] + 1);
else qmafront[i] = max(qmafront[i], 1);
}
}
cout << qmafront.back() << '\n';
}
else {
sort(q.begin(), q.end(), cmp);
vector<int> qfs;
for (pair<int, int>& i : q) {
i.first = lower_bound(xs.begin(), xs.end(), i.first) - xs.begin();
i.second = lower_bound(xs.begin(), xs.end(), i.second) - xs.begin();
qfs.push_back(i.first);
}
sort(qfs.begin(), qfs.end());
qfs.erase(unique(qfs.begin(), qfs.end()), qfs.end());
vector<int> prema(qfs.size());
int ltoqidx = 0;
for (int i = 0; i < qfs.size(); i++) {
qfidx[qfs[i]] = i;
}
int zeroidx = -1, ans = 0;
for (int i = 0; i < qfs.size(); i++) {
while (zeroidx + 1 < xs.size() && sptable[0][zeroidx + 1] < qfs[i] && sptable[0][zeroidx + 1] != -1) {
for (int j = 0; ; j++) {
if (sptable[j + 1][zeroidx + 1] == -1 || sptable[j + 1][zeroidx + 1] >= qfs[i]) {
ans += 1 << j;
zeroidx = sptable[j][zeroidx + 1];
break;
}
}
}
prema[i] = ans;
}
while (zeroidx + 1 < xs.size() && sptable[0][zeroidx + 1] != -1) {
for (int j = 0; ; j++) {
if (sptable[j + 1][zeroidx + 1] == -1) {
ans += 1 << j;
zeroidx = sptable[j][zeroidx + 1];
break;
}
}
}
for (int i = 0; i < q.size(); i++) {
while (ltoqidx < qfs.size() && qfs[ltoqidx] <= q[i].second) {
ltoqidx++;
}
int tidx = q[i].second, tmp = prema[qfidx[q[i].first]] + 1;
for (int j = ltoqidx; j < qfs.size(); j++) {
while (tidx + 1 < xs.size() && sptable[0][tidx + 1] != -1 && sptable[0][tidx + 1] < qfs[j]) {
for (int spi = 0; ; spi++) {
if (sptable[spi + 1][tidx + 1] == -1 || sptable[spi + 1][tidx + 1] >= qfs[j]) {
tmp += 1 << spi;
tidx = sptable[spi][tidx + 1];
break;
}
}
}
prema[j] = max(prema[j], tmp);
}
while (tidx + 1 < xs.size() && sptable[0][tidx + 1] != -1) {
for (int j = 0; ; j++) {
if (sptable[j + 1][tidx + 1] == -1) {
tmp += 1 << j;
tidx = sptable[j][tidx + 1];
break;
}
}
}
ans = max(ans, tmp);
}
cout << ans << '\n';
}
}
}
return 0;
}
3번 점 잇기 - WA
우선 같은 색의 정점들이 붙어있으면 당연하게도 교차점이 생기지 않는다. 그리고 더 멀리 가로지르는 간선일수록 다른 간선과 교차할 확률이 높아지니 왼쪽 혹은 오른쪽에 가장 가까운 정점 둘중 하나에 간선을 이어야 한다는 추측을 해 보았다. 또 이렇게 하면 하나의 간선은 최대 한번만 다른 간선과 교차하게 될것 같았고 대충 2개 이상의 같은색이 인접한 경우를 전부 제거하고 빈자리에서 새로 만나는 같은색들도 계속 제거하는 것을 반복하여 최종 결과에서 그리디를 돌리는 코드를 짜 보았다.
놀랍게도 이 풀이는 정해가 맞았고 더욱 놀랍게도 대회가 끝날때까지 부분점수를 전혀 받지 못하였다... 쓸데없이 복잡한 구현방식을 택한 바람에 인접한 같은 수를 제거한다는 간단한 코드가 제대로 작동하지 않는 참사가 벌어졌다. 3솔이면 부분점수를 더 긁지 못해도 첫 도전에 높은 상을 탔을텐데 풀이를 듣고 상당히 아쉬웠다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N;
string S;
cin >> N >> S;
deque<char> tmp;
char last = ' ', f;
for (char i : S) {
if (last == i || (tmp.size() && tmp.back() == i)) {
if (tmp.size() && tmp.back() == i) tmp.pop_back();
last = i;
}
else {
if (last == ' ') f = i;
tmp.push_back(i);
last = i;
}
}
deque<char> tmp2 = tmp, tmp3 = tmp, tmp4 = tmp;;
if (tmp.size() && tmp.back() != last) tmp2.push_back(last);
if (tmp.size() && tmp.front() != f) tmp3.push_front(f);
if (tmp.size() && tmp.front() != f && tmp.back() != last) {
tmp4.push_front(f);
tmp4.push_back(last);
}
int ans;
while (tmp.size() && tmp.front() == tmp.back()) {
tmp.pop_back();
if (tmp.size()) tmp.pop_front();
}
while (tmp2.size() && tmp2.front() == tmp2.back()) {
tmp2.pop_back();
if (tmp2.size()) tmp2.pop_front();
}
while (tmp3.size() && tmp3.front() == tmp3.back()) {
tmp3.pop_back();
if (tmp3.size()) tmp3.pop_front();
}
while (tmp4.size() && tmp4.front() == tmp4.back()) {
tmp4.pop_back();
if (tmp4.size()) tmp4.pop_front();
}
ans = min(min((tmp.size() / 2 + 1) / 2, (tmp2.size() / 2 + 1) / 2), min((tmp3.size() / 2 + 1) / 2, (tmp4.size() / 2 + 1) / 2));
cout << "Case #" << t << '\n';
cout << ans << '\n';
}
return 0;
}
4번 접두사와 접미사 - TLE
처음에는 kmp 변형에 dp를 섞으면 만점 풀이가 나올것 같았다. 그러나 이와 똑같은 문제를 코드포스인지 앳코더인지 kmp로 시도하다 퍼포가 나락갔던 기억이 되살아났고 (내가 KMP 말고는 전부 까먹은)SA같은 고급 문자열 알고리즘이 필요하다는걸 깨달아 길이가 짧은 처음 두 섭테만을 목표로 코드를 짜기 시작했다. 그리고 내가 플레, 다이아 자료구조보다 두배 이상 실수를 자주하는게 kmp인데 이번에도 뭔가 잘못되었는지 시간초과를 디버깅하는데 실패했고 결국 1번 섭테의 완탐을 짤 기력도 남기지 못하고 대회 시간의 남은 절반이 끝났다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N;
string A, B, C;
cin >> A >> B >> C;
long long ans = 0;
if (A.size() <= 100 && B.size() <= 100 && C.size() <= 100) {
vector<int> kmp(C.size());
for (int i = 1; i < C.size(); i++) {
kmp[i] = kmp[i - 1];
while (kmp[i]) {
if (C[kmp[i]] == C[i]) break;
kmp[i] = kmp[kmp[i]];
}
if (C[kmp[i]] == C[i]) kmp[i]++;
}
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
string AB;
for (int ai = 0; ai <= i; ai++) {
AB.push_back(A[ai]);
}
for (int bi = 0; bi <= j; bi++) {
AB.push_back(B[bi]);
}
int cidx = 0;
vector<int> cmp(AB.size());
for (int abi = 0; abi < AB.size(); abi++) {
while (C[cidx] != AB[abi] && cidx) {
cidx = kmp[cidx];
}
if (AB[abi] == C[cidx]) {
cmp[abi] = ++cidx;
if (cidx == C.size()) cidx = kmp[cidx - 1];
}
}
ans += cmp.back();
//cout << i + 1 << ' ' << j + 1 << ' ' << cmp.back() << '\n';
}
}
}
cout << "Case #" << t << '\n';
cout << ans << '\n';
}
return 0;
}
심지어 끝나고 확인해보니 이번 대회의 패널티 기준이 어떠한 조건도 없이 "모든 제출 * 7분"이라는 난생 처음보는 사악한 기준이라 중간에 나가느니만 못한(그럴수 있는건 아니지만) 120분동안 점수+0, 패널티 56분(8회) 라는 결과가 나와서 이걸 실망을 해야할지 아니면 그래도 첫 시도에 5등상 가능성이 보이기는 하는 결과에 만족해야 할지 심란했다.
고등학교때부터 느낀부분이지만 확실히 서브테스크의 중요도가 높은 대회는 나와 잘 맞지 않는것같다.
'대회 후기' 카테고리의 다른 글
| 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 |
| 2021년 정올 본선 2번 그래프 균형 맞추기 (0) | 2021.07.26 |
| 2021년 정올 본선 1번 헬기 착륙장 (0) | 2021.07.26 |
