2022 LG CNS CODEMONSTER 예선 후기

2017년, 내가 알고리즘을 공부하면서 처음 참가해봤었던 대회였다. 당시엔 진짜 아무것도 심지어 DFS BFS의 개념도 모르던 시절이라 선배들이 참여하던거 구경만 했던 기억이 있다. 3시간인지 5시간인지 기억은 잘 안나는데, 그 당시 느낌으로는 몇 시간동안 앉아서 코딩한다는 것을 상상을 못 하던 시절이라 다들 대단해 보였었다. 대단한 분들이 맞긴하지만..

 

첫 알고리즘 대회이자 끝 알고리즘 대회가 아닐까 싶다. 물론 아직 ICPC가 남아있긴 하지만 개인적으로는 대회보다는 축제의 느낌에 더 가깝다 생각하고, 팀플레이기 때문에..

아무튼 개인적으로 상당히 의미있는 대회다.

 

# 1번

---

주어진 구슬을 주어진 조건에 따라 일렬로 구성할 때 조건에 맞는 구슬 배열을 출력하는 문제다.

여기서 조건이란,

• 어떤 한 점을 기준으로 양 옆의 구슬 점수의 합이 같으며,
• 그런 구슬 배열이 많을 경우 좌우 구슬의 차이가 적은 배열을,
• 더 많은 구슬을 사용한 배열을,
• 총 구슬의 합이 더 무거운 배열을,
• 점수가 사전순으로 더 빠른 배열을

출력하는 것이다.

 

조건이 많이 까다로워서 구현량이 은근히 있다는 점을 제외하면 완전탐색이기 때문에 풀이는 쉽다. 다만, 재귀적으로 nPr을 구현해야하는데 조금 귀찮아서 next_permutation으로 9! * 9에 구했다. 최종 시간복잡도는 n! * n * n이다. 풀이는.. 생략

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

int n;
int gap = INF;
int sum = 0;
vector<int> answer;

void get(const vector<int>& marbles, int size) {
    vector<int> idx;
    for (int i = 0; i < n; ++i) {
        idx.emplace_back(i);
    }
    do {
        int s = 0;
        int lS = 0;
        int l = 0;
        int rS = 0;
        int r = size;
        for (int i = 0; i < size; ++i) {
            rS += marbles[idx[i]];
            s += marbles[idx[i]];
        }
        for (int i = 0; i < size; ++i) {
            r -= 1;
            rS -= marbles[idx[i]];
            if (lS == rS) break;
            l += 1;
            lS += marbles[idx[i]];
            if (lS == rS) break;
        }
        if (lS != rS) continue;
        vector<int> current(size, 0);
        for (int i = 0; i < size; ++i) current[i] = marbles[idx[i]];
        if (gap > abs(l - r)) {
            gap = abs(l - r);
            answer = current;
            sum = s;
        } else if (gap == abs(l - r)) {
            if (sum < s) {
                answer = current;
                sum = s;
            } else if (sum == s) {
                if (answer > current) {
                    answer = current;
                }
            }
        }
    } while (next_permutation(all(idx)));
}
vector<int> solution(vector<int> marbles) {
    n = marbles.size();
    for (int i = n; i >= 1; --i) {
        get(marbles, i);
    }
    return answer;
}
#if defined(BOJ) || defined(DEBUG)
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    vector<int> marbles = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    do {
        for (int i = 1; i <= marbles.size(); ++i) {
            clock_t start = clock();
            vector<int> res = solution(vector<int>(marbles.begin(), marbles.begin() + i));
            double time = (double)(clock() - start) / CLOCKS_PER_SEC;
            if (time >= 2.0) {
                for (auto e : vector<int>(marbles.begin(), marbles.begin() + i)) {
                    cout << e << ' ';
                }
                cout << endl;
                cout << time << endl;
            }
        }
    } while(next_permutation(all(marbles)));
    // for (auto e : res) cout << e << ' ';
    return 0;
}
#endif

 

# 2번

---

최대 5구를 갖는 멀티탭이 트리형태로 연결되어 있다. 각 구에는 다른 멀티탭을 연결시키거나 전자기기를 연결시킬 수 있는데, 각 전자기기는 모두 $k$W소모 하게 된다. 각 멀티탭마다 감당가능한 최대 전력이 주어질 때, 전자기기를 최소로 제거하여 모든 멀티탭이 전력을 감당할 수 있도록 만드는 문제다.

 

DFS+ 그리디로 풀 수 있다. 가장 하위 멀티탭의 전자기기를 제거하는 것이 무조건 이득이므로, DFS로 탐색한 뒤 멀티탭의 용량보다 초과하게 된다면 전자기기를 그 만큼 제거하고, 제거한 만큼 반환하여 누적시켜 부모와 조상에게 전파하는 방식으로 구할 수 있다. 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 INF (INT_MAX / 2)
#define all(x) (x).begin(), (x).end()
#define MAX_N 10'005
    int n;
int k;
// first는 뽑은 개수, second는 그래도 남은 갯수
pii dfs(const vector<int>& limits, const vector<vector<int>>& adj, int here) {
    int plugged = 0;
    int unPlugged = 0;
    for (int i = 0; i < 5; ++i) {
        plugged += (adj[here - 1][i] == -1);
        if (adj[here - 1][i] > 0) {
            pii res = dfs(limits, adj, adj[here - 1][i]);
            unPlugged += res.first;
            plugged += res.second;
        }
    }
    int gap = (plugged * k - limits[here - 1]);
    int hereUnplugged = gap / k + (gap % k ? 1 : 0);
    if (gap > 0) {
        unPlugged += hereUnplugged;
        plugged -= hereUnplugged;
    }
    // cout << pii(here, gap) << ": " << plugged << ", "<< pii(unPlugged,
    // plugged) << endl;
    return pii(unPlugged, plugged);
}
int solution(int K, vector<int> limits, vector<vector<int>> sockets) {
    int answer = 0;
    k = K;
    n = limits.size();
    answer = dfs(limits, sockets, 1).first;
    return answer;
}
#if defined(BOJ) || defined(DEBUG)
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << solution(300, {2000, 1000, 3000, 200, 600, 500},
                     {{2, 3, -1, -1, -1},
                      {4, 0, -1, -1, 6},
                      {5, 0, 0, 0, 0},
                      {-1, 0, 0, 0, 0},
                      {-1, -1, -1, -1, -1},
                      {-1, -1, 0, 0, 0}})
         << endl;
    return 0;
}
#endif

 

# 3번

---

두 문자열 $A$, $B$가 주어진다. $B$문자열 점프를 하며 $B$문자열을 모두 탐색하려고 한다. $B$ 위의 지점 $i$에서 점프할 수 있는 거리는 $B[i:]$와 ($A$의 공통 부분 문자열)의 크기만큼 점프할 수 있다. 점프를 통해 끝까지 도달 했을 때 한 점프 중 가장 작은 점프의 길이가 점수라고 할 때, 최대 점수를 구하는 문제다.

 

$N \times M$ 2차원 DP로 $A[j]$와 $B[i]$로 시작하는 문자열 중 최장 공통 접두사의 길이를 쉽게 구할 수 있다. 그 다음, $N$ 1차원 DP로 $i$에서 시작해서 얻을 수 있는 최대 점수를 구할 수 있다. 점화식은 아래 코드를 통해 확인하자!

 

처음에는 문자열문제인 줄 알고 설명만 읽고 넘겼는데, NM 제한이 생각보다 작아서 2차원 DP테이블 구성이 가능하고, 2차원 DP테이블을 구성하면 답을 구하는 건 쉽게 할 수 있을 것 같아서 접근해봤다. 생각보다 빠르게 풀렸다.

#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 10'005
int n, m;
string reference, track;
int dp[MAX_N][105];
int dp2[MAX_N];
int getDp(int i1, int i2) {
    if (i1 == n || i2 == m) return 0;
    int& ret = dp[i1][i2];
    if (ret != -1) return ret;
    ret = 0;
    if (track[i1] == reference[i2]) ret = getDp(i1 + 1, i2 + 1) + 1;
    return ret;
}
int getDp2(int i1) {
    if (i1 == n) return INF;
    int& ret = dp2[i1];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < m; ++i) {
        int jump = getDp(i1, i);
        if (jump) {
            ret = max(ret, min(getDp2(i1 + jump), jump));
        }
    }
    return ret;
}
int solution(string _reference, string _track) {
    int answer = 0;
    reference = _reference;
    track = _track;
    n = track.size();
    m = reference.size();
    memset(dp, -1, sizeof(dp));
    memset(dp2, -1, sizeof(dp2));
    return getDp2(0);
}
#if defined(BOJ) || defined(DEBUG)
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << solution("abc", "bcab") << endl;
    cout << solution("vxrvip", "xrviprvipvxrv") << endl;
    return 0;
}
#endif

 

# 4번

---

구성된 트리의 root를 계속 바꿀 수 있다. root가 변경될 때 마다 부모-자식 관계가 바뀌는 edge들을 세고, 각 edge당 몇 번 관계가 바뀌는지 구하는 문제다.

 

잘 살펴보면 현재 root에서 다음 root로 변경될 때 부모-자식 관계가 바뀌는 edge들은 현재 root와 다음 root 사이의 경로에 있는 edge들 임을 알 수 있다. 트리 위에서 경로를 구하는 것은 LCA로 해결이 가능하고, edge에 값을 update해주는 것은 IMOS법으로 u, v에 +1을, lca에 -2를 더해서 구할 수 있다.

 

안타깝게도 풀지 못 했다. LCA까지는 생각해냈는데, 구현하고 나니 10분밖에 안 남아서 대충 TLE가 뜨지만, O($N^2$)풀이로 제출했다. LCA + IMOS인것 같다는 생각을 하기는 했는데 LCA 디버깅하는데 혼을 다 써버려서 시간이 부족했다… 20분 정도 지나니 IMOS법이 맞다는 확신이 들어서 구현해보니 시간내에 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 150'005

const int maxLevel = (int)floor(log2(MAX_N));

int n; //  n : node 개수
int depth[MAX_N]; // 각 노드의 depth
int ac[MAX_N][20]; // 각 노드의 2^j번째 조상
vector<int> adj[MAX_N]; // 인접 리스트

map<pii, int> cnt;
int value[MAX_N];

void getTree(int here, int parent) {
	depth[here] = depth[parent] + 1;
	ac[here][0] = parent;

	for (int i = 1; i <= maxLevel; i++)
		ac[here][i] = ac[ac[here][i - 1]][i - 1];

	for (int i = 0; i < adj[here].size(); i++)
		if (adj[here][i] != parent)
			getTree(adj[here][i], here);
}

int getLca(int a, int b) {
	if (depth[a] != depth[b]) {
		if (depth[a] > depth[b])
			swap(a, b);

		for (int i = maxLevel; i >= 0; i--)
			if (depth[a] <= depth[ac[b][i]])
				b = ac[b][i];
	}

	int lca = a;
	if (a != b) {
		for (int i = maxLevel; i >= 0; i--) {
			if (ac[a][i] != ac[b][i]) {
				a = ac[a][i];
				b = ac[b][i];
			}
			lca = ac[a][i];
		}
	}

	return lca;
}

void get(int here, int to) {
    
    if (here == to) return;
    int p = ac[here][0];
    if (p == 0) return;
    cnt[pii(here, p)]++;
    get(p, to);
}

int dfs(int here, int parent) {
    int res = value[here];
    for (auto e : adj[here]) {
        if (e == parent) continue;
        int v = dfs(e, here);
        cnt[pii(here, e)] += v;
        res += v;
    }
    return res;
}

vector<int> solution(vector<vector<int>> edges, vector<int> roots) {
    n = edges.size() - 1;
    vector<int> answer;
    for (vector<int>& e : edges) {
        adj[e[0]].emplace_back(e[1]);
        adj[e[1]].emplace_back(e[0]);
    }

    depth[0] = -1;
    getTree(roots.back(), 0);

    for (int i = 0; i < roots.size(); ++i) {
        int lca = getLca(roots[i], (i == 0 ? 1 : roots[i - 1]));
        value[lca] -= 2;
        value[roots[i]] += 1;
        value[(i == 0 ? 1 : roots[i - 1])] += 1;
    }

    dfs(roots.back(), 0);

    for (vector<int>& e : edges) {
        answer.emplace_back(cnt[pii(e[0], e[1])] + cnt[pii(e[1], e[0])]);
    }

    return answer;
}

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

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

    // vector<vector<int>> edges;
    // for (int i = 1; i <= 150'000; ++i)
    //     edges.push_back({i, i + 1});

    // vector<int> roots;
    // for (int i = 0; i < 150'000; ++i)
    //     roots.emplace_back(i % 2 ? 1 : 150'001);
    // for (auto e : solution(edges, roots)) {
    //     cout << e << ' ';
    // }
    // cout << endl;

    // for (auto e : solution({{1, 3}, {1, 2}, {2, 4}, {2,5 }}, {2, 3})) {
    //     cout << e << ' ';
    // }
    // cout << endl;

    for (auto e : solution({{1, 2}, {1, 3}, {2, 4}}, {3, 4, 1, 2})) {
        cout << e << ' ';
    }
    cout << endl;

    return 0;
}
#endif