ICPC Seoul Regional 2019 (Online Mirror)::::Gratus' Blog

ICPC Seoul Regional 2019 (Online Mirror)

알고리즘 문제풀이/대회 후기, 문제풀이 2019. 11. 10. 00:41

본선 진출에 실패했기 때문에 (ㅠㅠ...) Online Mirror로 30분 늦게 팀으로 참여헀다. 나름 재밌긴 했는데, 본선 아쉽기도 했고 마지막에 2시간 정도를 아무것도 못하다보니 집중력이 너무 많이 떨어졌다.

Frozen 이전 시점 기준으로는 본 대회 스코어보드 대입했을 때 23등인데, 마지막 2시간동안 아무것도 하지 못했으므로 아마 실제로는 3x등 정도가 아닐까 싶다.

A. Fire on Field

Solve : Gratus907, Diordhd, Coffeetea

Code : Gratus907

시작하자마자 풀만 해 보이길래 셋이 같이 잠깐 보고 넘어갔다.

$a_0 = a_1 = 1$ 로 시작해서, 다음과 같이 $a_i$ 를 정의한다.

$a_i$ = 모든 $0 < k$ 에 대해, $a_{i}, a_{i-k}, a_{i-2k}$ 가 등차수열을 이루지 않게 하는 최소의 값.

$a_n$ 을 구하는 문제.

모든 $k$를 돌면 $a_i$ 로 가능한 값 하나를 도는 데 (즉, 어떤 $t$가 $a_i$ 로써 valid 한지 검증하는 데 ) $O(n)$ 이 걸리므로, $O(n^2 A)$ 시간에 naive하게 돌 수 있다. $n = 1000$이므로 $A$의 값이 중요한데, 주어진 그림을 보면 1000 정도의 $n$으로는 슥 봐도 몇백 이내에 값이 나오는 것으로 보이고, $n$을 실제로 다 돌 것도 아니므로 생각보다 소요 시간이 작다.

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

int A[1050];
int main()
{
    int n;
    scanf("%d",&n);
    A[0] = 1;
    A[1] = 1;
    for (int i = 2; i<=1010; i++)
    {
        for (int k = 1; k<= 500; k++)
        {
            bool flag = true;
            for (int j = 1; j*2<=i; j++)
            {
                if (k-A[i-j]==A[i-j]-A[i-2*j])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                A[i] = k;
                break;
            }
        }
    }
    printf("%d\n",A[n]);
}

J. Triangulation

Solve : Gratus907, Diordhd

Code : Gratus907

Diordhd가 다 풀어놓고 잠깐 나갔다 온 사이에 내가 뭔가 싶어서 읽어보고 컴퓨터를 슬쩍해서 맞았다 (.....)

$n$각형을 삼각형으로 쪼개는데, 쪼갠 다음 한 삼각형에서 다른 삼각형으로 갈 때 넘어야 하는 선분 개수의 최댓값을 분할 삼각화 지름이라고 하자. $n$각형에 대해서 이를 최소화하는 방법을 찾는 문제.

6각형으로 그려보면 쉬운데, 대충 삼각형으로 슥슥 쪼개면 $f(6) = 3$ 인데 문제에서 $f(6) = 2$ 임을 줬기 때문에 파악할 수 있다. 하나씩 건너뛰면서 그리는 것이 최선이며 (정6각형에서 출발하면, 가운데 정삼각형과 주변에 삼각형 3개) 왜 그런지는 조금 생각해 보면 어렵지 않다.

이제, 변이 더 많은 도형의 경우 저렇게 쪼개면 안쪽에는 $n/2$ 각형이 생기며 (7각형 같은건 4가 되니까, 엄밀히는 $(n+1)//2$ 이다.) 그 안에서 작은 도형을 삼각화하면 또 최선의 해답이 되므로 쉽게 재귀함수를 돌려 $O(\log n)$에 구하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int eval(int n)
{
    if (n <= 3) return 0;
    if (n == 4) return 1;
    else return eval((n+1)/2)+2;
}
int32_t main() 
{
    int n,i;
    scanf("%lld",&n);
    printf("%lld",eval(n));
}

L. What’s Mine is Mine

Solve : Gratus907, Coffeetea, Diordhd,

Code : Gratus907

내가 코딩이 빠를거같아서 내가 짜긴 했지만, 대충 세명이 같이 생각해서 비슷한 시점에 세명 모두 어떻게 풀지 이해했다.

dp[i] 를 $i$시점에서 어떻게든 얻을 수 있는 최댓값이라고 하면, 각 블록들을 적당히 택해서 이 최댓값들을 갱신해야 한다. 무조건 먼저 끝나는 블록부터 갱신하는 것을 원칙으로 하자.

또한, 갱신하기 위해서는 블록의 시작 시점에서의 최댓값을 알아야 한다. 만약 이 최댓값을 아직 모른다면 갱신이 불가능하므로, 블록들을 모두 정렬해 놓고 매 블록을 확인할 때마다 그 시작점까지의 값을 모두 지금까지의 최대로 갱신해 주어야 한다. 즉, 1~3 블록을 넣어서 dp[3]까지를 갱신했는데 다음 블록이 5~8이라면, 4와 5가 아직 갱신 안된 상태이므로 3에서부터 출발해서 5까지를 갱신해 준다는 뜻이다.

이렇게 하면 각 시점의 갱신 횟수가 많지 않으므로 매우 빠르게 답을 얻을 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
struct block
{
    int s, e, tp;
    bool operator<(const block&other)
    {
        if (e != other.e) return e< other.e;
        return (s < other.s);
    }
};
int dp[15200];
bool visit[15200];
int price[120];
int pt = 1;
vector <block> v;
int32_t main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i<=n; i++)
        cin >> price[i];
    for (int i = 0; i<m; i++)
    {
        int s, e, tp;
        cin >> s >> e >> tp;
        v.push_back({s,e,tp});
    }
    visit[0] = true;
    sort(v.begin(),v.end());
    for (auto it:v)
    {
        while(pt<=it.s)
        {
            dp[pt] = max(dp[pt],dp[pt-1]);
            pt++;
            visit[pt] = true;
        }
        dp[it.e] = max(dp[it.e],dp[it.s]+(it.e-it.s)*(price[it.tp]));
    }
    while(pt<=15000)
    {
        dp[pt] = max(dp[pt],dp[pt-1]);
        pt++;
        visit[pt] = true;
    }
    cout << dp[15000];
}

I. Thread Knots

Solve : Coffeetea, Diordhd, Gratus907

Code : Gratus907

한 실에 하나씩 점을 찍어서, 점들 간 간격의 최솟값을 최대화하는 문제.

뭔가 최솟값을 최대화한다는 세팅은 보통 파라메트릭 서치에서 사용하므로 일단 어떤 $T$를 답으로 할 수 있는지

(즉, 최솟값이 $T$보다 클 수 있는지) 를 빠르게 판정할 수 있다면 파라메트릭으로 풀 수 있다.

주어진 조건 하에서 실에 찍을 수 있는 최대한 앞에 점을 찍으면서 나아가는 식으로 이를 $O(n)$ 에 판정할 수 있으므로, 주어진 실 구간들을 정렬한 다음 파라메트릭 돌리면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
using pii = pair<int, int>;
pii arr[101010];
int n;

bool able(int x)
{
    int cur = arr[0].first;
    for (int i = 1; i<n; i++)
    {
        int u = cur+x;
        if (u > arr[i].second)
        {
            return false;
        }
        cur = max(u,arr[i].first);
    }
    return true;
}
int32_t main()
{
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        int t;
        cin >> arr[i].first >> t;
        arr[i].second = arr[i].first + t;
    }
    sort(arr, arr+n);
    int lo = 0, hi = 1e10; 
    while(lo + 1 < hi)
    {
        int mid = (lo + hi)/2;
        if (able(mid))
            lo = mid;
        else hi = mid;
    }
    cout << lo << '\n';
}

B. Gene Tree

Solve : Diordhd, Gratus907, Coffeetea

Code : 컴퓨터는 내가 잡았지만 사실상 다같이 코딩잡았다.

어떤 트리가 주어지는데, 이 트리는 모든 노드의 Degree가 1 또는 3이다. (즉, 리프를 하나 잡고 들어올리면 이진 트리가 된다) 이때 이 트리에서 모든 리프 노드 (Deg = 1 인 노드) 들끼리 서로 간의 거리의 제곱의 합을 구하는 문제.

처음에 Diordhd가 Centroid decomposition을 이용해서 재귀적으로 풀 수 있는 방법을 찾았는데, 절대 구현 못 할 것 같아서 한참 더 고민했다. 일단 기본 원리는 좌우 서브트리의 값을 이용해서 전체의 값을 구하는 트리 DP이고, 이 트리 DP를 어떻게 잘 해야 Centroid decomposition같은걸 하지 않고 짤 수 있을지 고민하다가 내가 다음 정보를 미리 전처리하고 나면 빠르게 계산할 수 있는 방법을 찾았고, Diordhd가 마지막 식정리를 빡세게 해줘서 코딩이 가능하게 만들어줬다.

- 지금 보고 있는 노드를 루트로 하는 서브트리에서, 리프노드의 개수

- 지금 보고 있는 노드를 루트로 하는 서브트리에서, 리프들까지의 거리의 합

- 지금 보고 있는 노드를 루트로 하는 서브트리에서, 리프들까지의 거리의 제곱 합

정리를 엄청 열심히 했는데 그만큼 뇌절도 많이 해서....

풀이 엄청 오래 걸리기도 했고, 엄청 고통받았다. 이런게 한 5장 더 있었다;;;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
using pii = pair<int, int>;

struct info
{
    int dsum, sqsum, leaf;
};
vector <pii> Tree[101010]; // (dest, weight)
int dist_from_root[101010], parent[101010];
int ans[101010];
info checker[101010];
bool visit[101010];
int root = 1;
int n;
queue <int> q;
void weight()
{
    dist_from_root[root] = 0;
    q.push(root);
    visit[root] = true;
    parent[root] = -1;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for (auto it:Tree[x])
        {
            if (!visit[it.first])
            {
                parent[it.first] = x;
                dist_from_root[it.first] = dist_from_root[x]+it.second;
                q.push(it.first);
                visit[it.first] = true;
            }
        }
    }
}
info func(int cur)
{
    if (Tree[cur].size() == 1)
    {
        checker[cur] = {0, 0, 1};
    }
    else 
    {
        vector <pii> v;
        for (auto it:Tree[cur])
            if (it.first!=parent[cur])
                v.push_back(it);
        info iA = func(v[0].first);
        info iB = func(v[1].first);
        int nn = iA.leaf + iB.leaf;
        int sr = iA.dsum + iB.dsum + (iA.leaf)*(v[0].second)+(iB.leaf)*(v[1].second);
        int sqr = iA.sqsum + iB.sqsum + (iA.leaf)*(v[0].second*v[0].second)
        +(iB.leaf)*(v[1].second*v[1].second) + 2*(iA.dsum*v[0].second + iB.dsum*v[1].second);

        int res = (iB.leaf)*(iA.sqsum+(iA.leaf)*(v[0].second*v[0].second) + 2*iA.dsum*v[0].second);
        res += (iA.leaf)*(iB.sqsum+(iB.leaf)*(v[1].second*v[1].second)+ 2*iB.dsum*v[1].second);   
        res += (2*(iA.leaf*v[0].second+iA.dsum)*(iB.leaf*v[1].second+iB.dsum));  
        ans[cur] = res;
        checker[cur]= {sr,sqr,nn};
    }
    return checker[cur];
}

int32_t main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i<n; i++)
    {
        int s, e, t;
        cin >> s >> e >> t;
        Tree[s].push_back({e,t});
        Tree[e].push_back({s,t});
    }
    for (int i = 1; i<=n; i++)
    {
        if (Tree[i].size() == 1) 
        {
            root = i; 
            Tree[root].push_back({0, 0});
            Tree[0].push_back({0, 0});
            break;
        }
    }
    weight();
    func(root);
    int final = 0;

    for (int i = 1; i<=n; i++)
    {
        final += ans[i];
    }
    cout << final << '\n';
}

아무튼 빡센 식정리 덕인지 코딩은 생각보다는 어렵지 않았다.

(대신 코드가 끔찍하다)

~~(근데 트리 DP는 그냥 너무 어려운거같다 ㅠㅠ)~~

B번 같은건 혼자 풀었으면 진짜 엄청 오래 걸렸을 것 같은데, 나름 풀이 construction이 잘 된 것 같다. 남은 시간 내내 H를 고민했는데 못푼건 아쉽지만 뭔가 2D에서 하는걸 너무 안풀어봐서 (구현이 귀찮아 보여서 던진게 많다) 그런 부족한 파트를 공부해야겠다는 생각도 들었다.

서울대에서 리저널 진출하려면 이정도 셋에서 7문제 정도는 풀어야 하는데, 2d 세그 같은 자료구조 공부들 좀 하고, 무엇보다 문제풀이에서 고민하는 시간을 많이 가져봐야 할 것 같다.

'알고리즘 문제풀이 > 대회 후기, 문제풀이' 카테고리의 다른 글

Google Hash Code 2020 후기 (0)	2020.02.21
Good Bye BOJ 2019 후기 (0)	2020.01.02
2019 ICPC 인터넷 예선 후기 (0)	2019.10.07
서울대학교 프로그래밍 경시대회 (SNUPC) Division 2 후기 (0)	2019.09.08
2019 함수컵 (FunctionCup) 후기 (0)	2019.09.02

Gratus' Blog