2022 ICPC Seoul Regional 본선 후기

나이 제한때문에 내가 참여할 수 있는 마지막 ICPC대회다. 4년이라는 대학생활 중 2번 밖에 참여하지 못 했지만, 마지막 참여라고 하니 조금 뒤숭숭한 느낌을 감출 수가 없다. ICPC뿐만 아니라 모든 PS대회들이 사실상 마지막 참여라서… 한 동안 정말 오버페이스로 온갖 대회들을 다 나간것 같다.

 

특히 올해는 학번때문에 반년간 같이 연습하던 팀원이 참여를 못 하게 되었고, 급하게 대체 팀원을 구해서 준비하게 되었다. 올해 초 부터 준비했던 팀원인데다가 UCPC 본선도 같이 참여할 만큼 나름대로의 팀워크가 잘 맞았었는데 급작스럽게 이런 일이 벌어지는 바람에 너무 당황스러웠다. 팀원 개인의 기량은 비슷한 것 같지만, 팀연습을 3~4번 밖에 못 한 관계로 팀워크는 사실상 없다고 봐도 무방했다. 그래도.. 그런 것 치고는 나쁘지는 않은 성적을 받은 것 같아 만족스럽다.

 

# J. Parentheses Tree(00:10)

---

트리를 괄호로 표현한 문자열이 주어진다. ()는 리프 노드를, (는 서브트리의 시작을, )는 서브트리의 끝을 나타낸다. 리프 노드의 depth의 합을 구하는 문제다.

 

간단하다. (마다 +1을 해주고, )마다 -1을, ()마다 현재 값을 더 해주면 끝이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif


#define all(x) (x).begin(), (x).end()
#define INF (INT_MAX / 2)
#define MAX_N 30'005

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    int cnt = 0;
    ll ans = 0;
    bool successive = false;
    char ch;
    while(cin>>ch) {
        if (ch == '(') {
            ++cnt;
            successive = false;
        } else {
            --cnt;
            if (!successive) {
                ans += cnt;
            }
            successive = true;

        }
    }
    cout << ans << endl;

    return 0;
}

 

# I. Palindrome Type(01:05) + 1

---

주어진 문자열에서 문자 $k(=0, 1, 2, 3)$개를 지워서 팰린드롬을 만들 수 있을 때, 최소 $k$를 구하는 문제다. 그런 $k$가 없을 경우 -1을 출력한다.

 

재귀적으로 $l, r$을 잡고 비교해나가면서 두 문자 $s[l], s[r]$이 같은 경우 $(l + 1, r - 1)$을 호출하고, 그렇지 않은 경우 $(l + 1, r), (l, r+ 1)$을 호출해나가며 $k$를 구하는 문제다.

 

재귀적으로 간단하게 풀 수 있는 문제인데, 본 대회를 치룰 때는 DP로 접근하는 바람에 엄청 복잡하게 풀었다. $dp[i][j][k]$를 정의해서 엄청 복잡하게 풀었는데, 덕분에 index 계산에서 실수하는 바람에 WA를 1번 받아버렸다. 다시 보니 진짜 쉽고 간단해서 빨리풀 수 있는 문제였는데, 괜히 내가 잡아서 늦게 푼데다가 1WA를 받는 바람에 팀 스코어에 폐를 끼치게 됐다….

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define INF (INT_MAX / 2)
#define MAX_N 1'000'005

string s;
int ans = INF;

void dfs(int l, int r, int cnt) {
    if (cnt > 3) return;
    if (cnt >= ans) return;
    if (l >= r) {
        ans = min(ans, cnt);
        return;
    }

    if (s[l] == s[r]) {
        dfs(l + 1, r - 1, cnt);
    } else {
	    dfs(l + 1, r, cnt + 1);
	    dfs(l, r - 1, cnt + 1);
    }
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
 
    cin >> s;
    dfs(0, s.size() - 1, 0);

    cout << (ans == INF ? -1 : ans) << endl;
 
    return 0;
}

 

# F. Frog Jump(01:10)

---

x축에 평행하게 연꽃이 놓여있다. 개구리는 겹쳐있는 연꽃 사이는 점프없이 걸어다닐 수 있다. 연꽃이 겹쳐있지 않아 떨어져있는 경우, 그 거리만큼 점프해서 지나갈 수 있다. 연꽃 번호로 이루어진 경로가 주어질 때, 해당 경로를 가기 위해서 최소한으로 해야하는 점프의 크기를 구하는 문제다.

 

먼저, 연속된 연꽃끼리는 모두 거리가 0으로 볼 수 있다. 그리고 떨어져 있는 연꽃집합사이를 점프할 때는 이웃한 연꽃집합을 통해서 점프해 가는 것이 최소 점프 크기임은 자명하다.

따라서 이웃한 연꽃집합 사이의 거리를 구하면 부분합을 통해서 두 연꽃 사이의 최소 점프 거리를 구할 수 있다.

 

나는 문제를 읽지도, 보지도 않았는데, I번에서 내가 해매고 있으니 그 다음으로 많이 푼 F번을 두 명이서 잡아서 부분합으로 바로 풀어버렸다. 아마 중간에 연속된 연꽃을 처리하면서 실수가 있어서 예제가 안 나오는 바람에 약간 오래 걸렸다고 얘기했던 것 같다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define INF (INT_MAX / 2)
#define MAX_N 100'005

int n, k;
int psum[MAX_N];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    cin >> n >> k;
    int prev = 0;
    for (int i = 1; i <= n; ++i) {
        pii a;
        cin >> a;
        psum[i] = psum[i - 1];
        if (i == 1) prev = a.second;
        if (prev < a.first) {
            psum[i] += a.first - prev;
        }
        prev = max(prev, a.second);
    }

    ll ans = 0;
    int here = 1;
    for (int i = 1; i <= k; ++i) {
        int to;
        cin >> to;
        ans += abs(psum[to] - psum[here]);
        here = to;
    }
    cout << ans << endl;
    

    return 0;
}

 

# K. Shuffle Game(02:28) + 1

---

문자열 $X$와 $P_1$, $P_2$가 주어진다. $P_1, P_2$의 각각의 문자를 큐 처럼 앞에서 부터 하나씩 뽑아 문자열을 새로 만들었을 때, 문자열 $X$와의 Longest Common Sequence를 구하는 문제다.

 

2개의 문자열에서 Longest Common Sequence를 구하는 점화식을 3개로 확장시키면 된다. 정말 이게 끝이다.

 

정말 간단했지만, 컨디션 조절 실패인지.. 그냥 멍청한 건지 1번 WA를 받았다.

분명 두 문자열이 독립적이기 때문에 LCS를 3개의 문자열에서 돌리면 될 것 같다는 가설을 세우고 코드를 짰는데… 다시 생각해보니 Sequence가 아니라 Substring을 구하는 코드를 짠 것 같다. 그러니 예제는 다 나오고 WA를 받은게 아닐까… 생각해본다.

다행히 유성님이 손으로 3차원 테이블을 다 채우셔서 차근차근 점화식을 풀어나가셔서 풀긴 했는데, 유성님 아니었으면 진짜 큰 일날 뻔 했다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define INF (INT_MAX / 2)
#define MAX_N 505

int n, p, q;
string arr[MAX_N];
string brr[MAX_N];
string crr[MAX_N];
int dp[MAX_N][MAX_N][MAX_N];

int getDp(int i1, int i2, int i3) {
    if (i1 == n) return 0;
    int& ret = dp[i1][i2][i3];
    if (ret != -1) {
        return ret;
    }

    ret = getDp(i1 + 1, i2, i3);
    if (i2 != p) {
        if (arr[i1] == brr[i2])
            ret = max(ret, getDp(i1 + 1, i2 + 1, i3) + (arr[i1] == brr[i2]));
        else
            ret = max(ret, getDp(i1 , i2 + 1, i3));
    }
    if (i3 != q) {
        if (arr[i1] == crr[i3])
            ret = max(ret, getDp(i1 + 1, i2, i3 + 1) + (arr[i1] == crr[i3]));
        else 
            ret = max(ret, getDp(i1 , i2, i3 + 1));
    }

    return ret;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
 
    cin >> n >> p >> q;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < p; ++i) {
        cin >> brr[i];
    }
    for (int i = 0; i < q; i++) {
        cin >> crr[i];
    }

    memset(dp, -1, sizeof(dp));
    cout << getDp(0, 0, 0) << endl;
 
    return 0;
}

 

# E. Forbidden Turns(03:00)

---

가중치가 있는 edge로 방향 그래프가 주어진다. 시작지점 $s$에서 도착지점 $e$로 가는 최단 경로를 구해야한다. 해당 그래프에서 금지된 회전($a \rightarrow b \rightarrow c)$가 주어지는데, 경로를 탐색하는 도중 $a \rightarrow b \rightarrow c$로 이동하는 경로가 존재하면 않된다. 즉, 현재 $b$에 있고, 이전에 $a$에서 왔을 때 $c$로 이동할 수 없다. 이때 최단 경로의 비용을 구하는 문제다(단, 각 vertex당 outdegree는 최대 10으로 제한된다).

 

문제 가장 아래에 조그맣게 제한으로 들어있는 outdegree가 최대 10이라는 조건 덕분에 쉽게 해결할 수 있다. dist배열을 그냥 map<int, int> dist[MAX_N]으로 관리하면 각 map에 해봤자 10개의 key만 삽입되므로 다른건 고려할 필요가 없어진다. 구현 코드만 약간 달라질 뿐 dist배열을 2차원으로 관리하는 것과 동일하다.

 

outdegree가 10이라는 조건을 비교적 늦게 발견하는 바람에 약간 시간이 오래걸렸다. 뿐만 아니라, 지금이야 dist를 map으로 관리하면 쉽게 구현가능하다는 걸 알고 있지만, 대회 당시에는 outdegree가 10이라는 조건으로 인해서 dist map이 key가 10개밖에 되지 않는다는 사실이 직관적으로 와닿지 않아서 그래프를 뒤집은 뒤, dist를 단순 2차원 배열로 관리하려다보니 구현이 너무 까다로웠었다.

outdegree 조건 발견 직후부터 set이나 map으로 관리하자고 주장하시던 유성님 말을 진작에 들었으면 조금 더 빨리풀 수 있지 않았을까 하는 아쉬움이 있다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
	os << pai.first << ' ' << pai.second;
	return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
	is >> pai.first >> pai.second;
	return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif


#define all(x) (x).begin(), (x).end()
#define INF (INT_MAX / 2)
#define MAX_N 30'005

int m, n, k;
int s, e;
vector<pii> adj[MAX_N];
vector<pii> forbiddens[MAX_N];

map<int, int> dist[MAX_N];
int dijkstra() {
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    dist[s][s] = 0;
    pq.emplace(0, pii(s, s));

    while(pq.size()) {
        int here = pq.top().second.first;
        int prev = pq.top().second.second;
        int hereCost = pq.top().first;
        pq.pop();

        if (hereCost > dist[here][prev]) continue;
        if (here == e) return hereCost;

        for (auto& e : adj[here]) {
            int next = e.first;
            int nextCost = hereCost + e.second;

            if (binary_search(all(forbiddens[here]), pii(prev, next))) continue;

            auto it = dist[next].find(here);
            if (it == dist[next].end() || it->second > nextCost) {
                dist[next][here] = nextCost;
                pq.emplace(nextCost, pii(next, here));
            }
        }
    }
    return -1;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    cin >> m >> n >> k;
    cin >> s >> e;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
    }
    for (int i = 0; i < k; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        forbiddens[b].emplace_back(a, c);
    }
    for (int i = 0; i < n; ++i) {
        sort(all(forbiddens[i]));
    }

    cout << dijkstra() << endl;

    return 0;
}