2022 ICPC Seoul Regional 예선 후기

오랜만에 아쉬움 없는 대회였다.

되돌아보면 작년보다 훨씬 쉬운 난이도였지만, 팀원 이슈 때문에 일주일전에 급조된 팀 치고는 괜찮은 팀워크를 보였고, 개개인의 역량은 충분히 발휘한 것 같다.

난이도만 보면 조금 고전한 느낌이 있지만, 더 시간을 줬어도 그 다음 난이도의 문제는 풀지 못 했을 것 같다는 생각이 들었다. 그렇게 따지면 어쨋거나 우리가 할 수 있는건 다 한거니까.. 후회없는 과정이었고, 후회없는 결과였다.

 

A. 양팔저울(+ 00:10)

조건에 따라 양팔저울에 자갈을 올려서 저울을 완성하고, 그 상태에서 무게를 평형으로 맞추기 위한 무게추의 최소 개수를 구하는 문제다. 무게추의 무게는 정해져있다.

“저울”이라는 단어 때문에 문제를 보자마자 bfs나 dp 또는 파라메트릭일 것이라는 생각부터 했는데, 단순 구현문제였다. 무게추의 무게 또한 $a_i ≤ a_{i - 1} * 3$이므로 단순히 구현만하면 풀 수 있다.

10분이나 걸렸는데, 5분정도 프린트하는 시간이 걸렸고, 조금 떠는 바람에(진짜 손을 달달달 떨었다) 문제 푸는데에 5분이 걸렸다.

#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 105

int n;
int weight[] = {100, 50, 20, 10, 5, 2, 1};

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

    cin >> n;
    int l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;

        if (l == r) l += a;
        else if (l > r) r += a;
        else l += a;
    }

    int diff = abs(r - l);
    int ans = 0;
    for (int i = 0; i < 7; ++i) {
        while(diff && diff >= weight[i]) {
            diff -= weight[i];
            ++ans;
        }
    }
    cout << ans << endl;

    return 0;
}

 

C. 컨테이너 재배치(00:39) + 1

항구의 각 슬롯에 컨테이너가 주어진대로 배치되어 있을 때, 슬롯 $i, j$에 대해 $|a_i - a_j| ≤ 1$이 되도록 컨테이너를 재배치하려고 한다. 컨테이너를 옮겨야하는 횟수를 구하는 문제다.

그림과 설명을 보자마자 든 생각은 ‘파라메트릭인가?’ 싶었다. 근데, 생각해보면 전체 컨테이너 수와 슬롯 수는 정해져있으니 가능한 높이는 (전체 컨테이너 수) / (슬롯 수) 를 $h$라 하면 $h$와 $h + 1$이다. 모든 슬롯의 컨테이너의 높이가 저 두 높이로 바뀌어야하므로, 그리디하게 $h + 1$보다 큰 슬롯은 $h + 1$로, $h$보다 작은 슬롯은 $h$로 맞춰주어야한다.

이 때 큰 슬롯의 컨테이너를 옮기면 작은 슬롯이 채워지고, 작은 슬롯의 컨테이너를 옮기면 큰 슬롯이 채워지는데, 그냥 for loop 돌면서 $h + 1$보다 큰 슬롯의 개수와 $h$보다 작은 슬롯의 개수를 세어주고, 둘 중 큰 개수가 정답이다. $h$와 $h + 1$의 두 높이 사이에서 컨테이너가 옮겨지는건 고려하지 않아도(이런 일이 일어나면 안 된다) 되기 때문이다.

 

처음에는 for loop을 돌면서 $h$보다 작은 슬롯의 개수만 세어줬는데 WA를 받았다. 1 2 3 5의 경우에 2를 출력해야 하는데 1을 출력함을 알았고, 위 풀이를 생각해냈다. 중간에 E를 잡는다고 시간을 많이 투자해서 많이 늦게 풀어서 약간 아쉽다는 생각을 한다.

#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

int n, m;
int arr[MAX_N];

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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        m += arr[i];
    }

    int h = m / n;
    int up = 0, down = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > h + 1) up += arr[i] - h - 1;
        else if (arr[i] < h) down += h - arr[i];
    }
    cout << max(up, down) << endl;

    return 0;
}

 

E. 선물할인(00:47) + 4

$n$개의 선물 중 $a$개를 반값 할인받을 수 있다. $b$의 예산으로 살 수 있는 최대 선물의 수를 구하는 문제다.

 

범주가 풀었는데, 풀이 설명할 때 C번 잡는다고 제대로 못 들었다. 업솔빙하면서 어떻게 풀어야할 지 감이 안 잡혀서 물어보니, 정렬 후 작은 $x$개를 선물한다고 가정하고, 그 $x$개 중 가장 비싼 $a$개를 반값할인 했을 때 $b$보다 적은 가격이 나오면 $x$개를 선물 가능하다고 한다. 따라서 $x$를 돌리면서 위 계산을 해주면되는데, 두 index를 관리하면서 투포인터처럼 해나가도 되고, 간단하게 partialSum을 이용해서 풀어줄 수도 있다.

 

4번이나 틀렸는데, partialSum계산 시 index관리 실패로 몇 번 틀린 것 같고, 자잘한 실수들때문에 틀린 것 같다. C번 이후 K번 잡는다고 신경을 아예 못 썼다.

#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, a, b;
int arr[MAX_N];
ll psum[MAX_N];

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

    cin >> n >> b >> a;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; ++i) {
        psum[i] = psum[i - 1] + arr[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ll price = psum[i] - (psum[i] - psum[max(i - a, 0)]) / 2;
        if (price <= b) ans = i;
    }
    cout << ans << endl;

    return 0;
}

 

F. Islands Tour(02:10) + 1

모든 V의 outgoing E가 1개 인 그래프가 주어지고 V 중복방문을 허용하지 않을 때, 한 번에 최대로 방문할 수 있는 V의 개수를 구하는 문제다.

 

사실 내가 잡은 문제가 아니라 같은 팀원이 잡은 문제라 문제 설명만 알고 있는 상태다. outgoing E가 1인걸 알지 못 했을 때는 SCC로 묶어서 DAG만든 뒤에 DP를 쓰는게 맞지않나 하는 의견을 냈었는데, outgoing E가 1이라 DFS로 충분히 가능하다는 말을 하시면서 잡으셨다. outgoing E가 1이므로 하나의 V는 단 하나의 cycle에만 속할 수 있으므로, cycle 판별 이후 같은 cycle 내에 있는 V들의 값을 같은 값으로 통일 시켜주고 DP처럼 타고 올라가면 되는 것 같다.

 

cycle 판별과 cycle내의 V관리 하시는데 약간 어려움을 겪으셔서 시간이 오래걸렸고, 같은 문제로 1WA를 받았다. 어차피 팀노트가 있어서 SCC로 묶은 뒤에 관리하면 더 빠르고 편했을 것 같은데, 그래도 정석풀이대로 정직하게 잘 푸셔서 다행이다. 업솔빙 시에는 SCC로 묶어서 풀었다.

#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

int m, n;

int cnt; // cnt : dfsn세기 위해 필요
int dfsn[MAX_N]; // dfsn
bool finished[MAX_N]; // scc가 구성됬는지 체크하는 배열
stack<int> st; // scc구성하기위해 필요
int sn[MAX_N]; // i번째 vertex가 들어간 scc의 번호
int adj[MAX_N]; // 인접리스트
vector<vector<int>> scc; // scc와 scc의 원소들을 저장

int dfs(int here) {
	dfsn[here] = ++cnt;
	st.push(here);

	int result = dfsn[here];
    int next = adj[here];
    if (next != -1) {
        if (dfsn[next] == 0)
            result = min(result, dfs(next));
        else if (!finished[next])
            result = min(result, dfsn[next]);
    }

	if (result == dfsn[here]) {
		vector<int> curScc;

		while (true) {
			int top = st.top();
			st.pop();
			curScc.push_back(top);
			finished[top] = true;
			sn[top] = scc.size();

			if (top == here)
				break;
		}

		sort(curScc.begin(), curScc.end()); // 순서대로 출력을 위해

		scc.push_back(curScc);
	}

	return result;
}

bool visited[MAX_N];
int ans[MAX_N];
void dfs2(int here) {

    visited[here] = true;
    ans[sn[here]] = scc[sn[here]].size();

    int next = adj[here];
    if (next == -1) return;
    if (!visited[next]) dfs2(next);
    if (sn[here] != sn[next]) ans[sn[here]] += ans[sn[next]];
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
 
    cin >> m >> n;
    memset(adj, -1, sizeof(adj));
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u] = v;
    }

    for (int i = 0; i < n; ++i) {
        if (dfsn[i] == 0)
			dfs(i);
    }

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs2(i);
        }
    }

    int res = 0;
    for (int i = 0; i < scc.size(); ++i) {
        res = max(res, ans[i]);
    }
    cout << res << endl;
 
    return 0;
}

 

K. 템포럴 그래프(02:41) + 4

각 시간마다 방문할 수 있는 E가 정해져있는데, 각 시간마다 방문할 수 있는 E중 1개만 방문할 수 있다. 시간이 증가하는 순서대로 방문해야할 때, 최단거리를 구하는 문제다.(설명이 너무 어려운데, 문제를 보는게 더 낫다)

 

시간 t에 방문할 수 있는 E중 단 1개만 방문하다는 사실을 망각한 채로 생각하다보니 다익스트라 T번 돌리는 풀이를 생각했는데, TLE를 받거나 WA를 받았다. 아무리 생각해도 이 풀이 말고는 방법이 없어서 상수커팅이나 spfa를 갈기려고 생각했는데, 시간 t에 방문할 수 있는 E가 1개 뿐이라는 점을 이용하면 BFS처럼 돌릴 수 있다.

 

내가 잡은 문젠데, 좀 많이 틀려서 팀원들한테 미안했다. 나는 끝까지 “BFS로 뭘 어쩌겠다는 거지?”하는 생각이 들어서 F번을 풀었던 팀원이 대신 잡아서 풀어줬는데, 빨리 푸셔서 정말 다행이라는 생각을 했다. 지금 보면 풀이가 바로 생각나는데, 긴장한 탓 때문인지 제 실력을 발휘하지 못 한것 같아서 약간? 아쉽다.

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

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

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

int n, t, m;
int s, e;
int dist[MAX_N];
int prevDist[MAX_N];

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

    cin >> n >> t >> m;
    cin >> s >> e;

    fill_n(prevDist, MAX_N, INF);
    fill_n(dist, MAX_N, INF);
    prevDist[s] = 0;
    dist[s] = 0;
    for (int i = 1; i <= t; ++i) {
        for (int j = 0; j < m; ++j) {
            int u, v, c;
            cin >> u >> v >> c;

            dist[u] = min(dist[u], prevDist[v] + c);
            dist[v] = min(dist[v], prevDist[u] + c);
        }
        copy_n(dist, n, prevDist);
    }
    
    cout << (dist[e] == INF ? -1 : dist[e]) << endl;

    return 0;
}

 

G. Jar Game(02:45)

F와 S가 번갈아 가면서 게임을 하는데, i(1, 2, …, )번째 턴에는 i개의 돌맹이만 가져갈 수 있다. 3개의 주머니에 각각 a, b, c개의 돌맹이 들어있고, F와 S는 매턴 아무 주머니에서 돌맹이를 i개를 가져간다. 만약 주머니에 돌맹이가 i개 미만으로 있을 경우 그냥 그 주머니의 돌맹이 전부를 가져간다. F와 S가 최선을 다 할 때 이기는 사람을 출력하는 문제다.

게임이론 필요없는 간단한 4차원 DP다.

DP[i][j][k][l] = i번째 턴에 j, k, l개의 돌맹이가 남았을 때 가져갈 수 있는 최대 돌맹이 수

이걸 그냥 문제 조건대로 풀어주면 끝이다.

문제가 간단해서 범주가 풀 수 있다고 잡았는데, 예제도 틀리는 바람에 시간이 오래걸렸다. 범주가 짠 코드를 보면 매턴 각자 최선을 다 할 때 가져갈 수 있는 (나의 최대 돌맹이)를 가져가는 것이 아니라, (나의 돌맹이 - 상대방의 돌맹이)의 최대를 가져가는 바람에 계속 예제가 틀렸다. 아무리 생각해도 그냥 매 턴 마다 자신의 돌맹이만 최대로 만들면 될 것 같은데 설득하기 힘들어서 K번을 풀 때 까지 기다리다가 K번 풀리자마자 내가 수정해서 AC를 받았다.

 

조금만 생각해보면 어차피 두 사람이 가져갈 수 있는 돌맹이의 합은 한정되어 있고, 자신만 최대로 가져가면 상대는 최소로 가져갈 수 밖에 없기 때문에 상대방의 돌맹이는 신경쓸 필요도 없다. 상대방 돌맹이를 신경쓰는 순간 아마도, 참조적 투명성이 깨지기 때문에… 라고 설득을 해봤었는데 맞는지는 나도 모르겠다.

#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 all(x) (x).begin(), (x).end()
#define MAX_N 101

int a, b, c;
int sum;
int dp[27][MAX_N][MAX_N][MAX_N];

int getDp(int round, int j1, int j2, int j3) {
    if (j1 == 0 && j2 == 0 && j3 == 0) {
        return 0;
    }

    int& ret = dp[round][j1][j2][j3];
    if (ret != -1) return ret;

    ret = 0;
    if (j1) {
        int g = min(j1, round);
        ret = max(ret, g + (j1 + j2 + j3) - getDp(round + 1, j1 - g, j2, j3));
    }
    if (j2) {
        int g = min(j2, round);
        ret = max(ret, g + (j1 + j2 + j3) - getDp(round + 1, j1, j2 - g, j3));
    }
    if (j3) {
        int g = min(j3, round);
        ret = max(ret, g + (j1 + j2 + j3) - getDp(round + 1, j1, j2, j3 - g));
    }
    return ret;
}

#if defined(BOJ) || defined(DEBUG)

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

    cin >> a >> b >> c;
    sum = a + b + c;
    memset(dp, -1, sizeof(dp));
    int res = getDp(1, a, b, c);

    if (res > sum / 2) cout << "F" << endl;
    else if (res == sum / 2) cout << "D" << endl;
    else cout << "S" << endl;

    return 0;
}
#endif