Codeforces Round #620 (Div. 2) 후기 + 풀이

오렌지 찍었다 :dhk:

한국인 세터 라운드라서 시간도 좋은 것 같아서, 오렌지까지 1점 남았지만 그냥 Div2 뛰기로 했다.

---

A. Two rabbits

두 토끼 사이의 거리 $d$가 $a+b$ 로 나누어 떨어지는지 확인하고, 되면 몫을 출력, 아니면 -1.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
 
void solve()
{
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    int d = y-x;
    int e = a+b;
    if (d%e)
    {
        cout << -1 << '\n';
        return;
    }
    else
    {
        cout << (d/e) << '\n';
        return;
    }
}
 
int32_t main()
{
    usecppio
    int t;
    cin >> t;
    while(t--) solve();
}

---

B. Longest Palindrome

문제 제목만 보면 Manacher 같은걸 써야 할 것 같은 문제지만...

대략적인 요점은, $n$개의 길이가 같은 문자열이 주어질 때 이들을 적당히 재배열해서 붙임으로써 최대한 긴 팰린드롬을 만들어야 하는 문제이다. 

어떤 문자열 $S$에 대해 $S_r$ 를 $S$의 반전이라고 할 때, $S$ 와 $S_r$ 이 모두 주어져 있다면 앞에 $S$를, 뒤에 $S_r$ 을 붙이는 식으로 항상 이 문자열들을 다 쓸 수 있다.

 

이것만 생각하면 틀리게 되는데, 다행히 예제 중에 이렇게만 짜면 틀리는 케이스가 있다. 스스로 팰린드롬인 문자열은 가운데에 한번에 한해서 넣을 수 있고, 어차피 모든 문자열의 길이가 같으므로 팰린드롬들 중 아무것이나 넣어도 된다.

 

분명히 쉬운 문제인데, 구현에서 조금 시간이 걸렸다. set <string> 쓸지 vector<string> 으로 전탐색할지도 아무거나 해도 되는데 쓸데없이 고민하고...

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
 
int n, m;
vector <string> v;
vector <string> self_palindromes;
vector <string> will_use;
bool got[120];
int32_t main()
{
    cin >> n >> m;
    for (int i = 0; i<n; i++)
    {
        string s;
        cin >> s;
        v.push_back(s);
    }
    for (int i = 0; i<n; i++)
    {
        if (got[i]) continue;
        string u;
        u = v[i];
        reverse(all(u));
        if (u == v[i])
        {
            self_palindromes.push_back(v[i]);
            got[i] = true;
            continue;
        }
        for (int j = 0; j<n; j++)
        {
            if (i == j) continue;
            if (got[j]) continue;
            if (u == v[j] && !got[j])
            {
                will_use.push_back(v[i]);
                got[i] = true; got[j] = true;
                break;
            }
        }
    }
    string ans = "";
    for (auto it:will_use)
    {
        ans += it;
    }
    string revans = ans;
    reverse(all(revans));
    if (!self_palindromes.empty())
        ans += self_palindromes[0];
    ans += revans;
    cout << ans.size() << '\n';
    if (ans.size()>0)
        cout << ans << '\n';
}

---

C. Air Conditioner

1분에 1씩 온도를 내리거나 올릴수 있는 상황에서, 들어오는 모든 요구를 만족시킬 수 있는지 확인하는 문제. 

시작 온도에서부터, 시점 $t$ 에 내가 만들 수 있는 최고 / 최저 온도의 범위를 계속 갱신할 수 있다. 새로 요구가 들어올 때, 그 요구를 만족시킬 수 있는지와 함께 내가 현재 시점에 요구를 만족시키면서 만들 수 있는 최고 / 최저 온도를 갱신한다. 예를 들어, 내가 $t = 4$ 에 [3, 7] 까지를 만들 수 있지만 요구가 [6, 11] 이라면, [6, 7] 에서부터 시작해서 다음 요청을 만족시킬수 있는지 판단하면 ok.

 

가끔 있는 구현 실수를 했는데, 앞으로 Input이 더 들어올 수 있는 문제의 경우 입력을 다 받지 않고 return이나 goto 같은걸로 끝내버리면 다음에 와야 할 입력 때문에 다음 케이스에서 틀리게 된다. multi testcase 형태의 문제에서 조금 조심해야 할듯. 예제는 왜맞지...

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
 
void solve()
{
    int n, m;
    cin >> n >> m;
    int lo = m, hi = m;
    int bef_time = 0;
    bool able = true;
    for (int i = 0; i<n; i++)
    {
        int ti, li, ri;
        cin >> ti >> li >> ri;
        int have_time = ti - bef_time;
        int nhi = hi+have_time;
        int nlo = lo-have_time;
        lo = max(nlo, li);
        hi = min(nhi, ri);
        bef_time = ti;
        if (hi >= lo) continue;
        else
            able = false;
    }
    if (able)
        cout << "YES\n";
    else
        cout << "NO\n";
}
 
int32_t main()
{
    usecppio
    int t;
    cin >> t;
    while(t--) solve();
}

---

D. Shortest and Longest LIS

$1$..$n$의 Permutation을 하나 찾는데, 

<와 >의 나열로 구성된 '제약 조건' 이 주어진다. 예를 들어, <>>>< 라면 a<b>c>d<e 가 만족되어야 한다.

- LIS가 가장 긴 such permutation

- LIS가 가장 짧은 such permutation.

약간 찍맞할 수 있는 문제이긴 한데, 찍어서 일단 코딩을 한 뒤에라도 증명하는 것은 별로 어렵지 않다. 핵심적인 아이디어는, 먼저 조건을 생각하고 LIS를 최대화 (최소화) 하는것이 어려우면 반대로 LIS를 최대화한 다음 조건에 맞게 조금만 변형할 방법을 찾으면 어떨까? 라는 생각이다. 

일단, LIS가 가장 길기 위해서는 1, 2, 3, 4, ... $n$ 형태의 permutation이 최고이다. 그런데, 이 Permutation이 조건을 만족하는지의 정보는 전혀 없다. 따라서, 조건을 만족하는 형태로 만들어 주기 위해 >가 있는 구간들을 잘 조정해 주면 된다. 구체적으로는 >가 연속해서 나오는 구간 [a, b] 를 반대로 뒤집어 주면 되는데, 예를 들어 

7 >><>>< 가 주어진 테스트케이스라면 ,먼저 1 2 3 4 5 6 7 을 만든 다음 앞의 >> 를 지키기 위해 (3 2 1) 4 5 6 7 로, 중간의 >> 를 또 지켜야 하므로 (3 2 1) (6 5 4) 7 로 만들어 주면 된다.

반대로 LIS가 최대한 짧고 싶다면, $n$ 부터 내려가는 Permutation에서 출발하여, <가 연속해서 있는 구간들을 반대로 뒤집는다. 앞서의 예시라면, 7 6 5 4 3 2 1 -> 7 6 (4 5) 3 (1 2) 형태로 뒤집어 주면 되겠다. 

 

증명을 하고자 한다면, 먼저 답을 정해놓고 검증하는 방법을 생각해 볼 수 있다. 즉, 그 '최댓값' 이나 '최솟값' 이 얼마일지 먼저 생각해 보고 위 순열이 이 값을 만족한다는 것을 보이는 것이 훨씬 쉽다. 

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
 
vector <int> min_case;
vector <int> max_case;
vector <pii> v, v2;
 
void vprint(vector <int> &a, int len)
{
    for (int i = 1; i<=len; i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
}
void solve()
{
    v.clear();
    v2.clear();
    min_case.clear();
    max_case.clear();
    int n;
    string s;
    cin >> n >> s;
    int minlis = 0;
    int maxlis = 1;
    int cnt = 0;
    min_case.resize(n+10);
    max_case.resize(n+10);
    for (int i = 0; i<n-1; i++)
    {
        if (s[i] == '<')
        {
            cnt++;
            maxlis++;
        }
        else
        {
            if (cnt>0)
            {
                v.push_back({i+1,cnt+1});
                minlis = max(minlis, cnt+1);
            }
            cnt = 0;
        }
    }
    v.push_back({n,cnt+1});
    minlis = max(minlis, cnt+1);
    cnt = 0;
    int cur_max = n;
    for (int i = 0; i<v.size(); i++)
    {
        pii p = v[i];
        v[i] = {p.first-p.second+1,p.first};
    }
    for (int i = 1; i<=n; i++)
    {
        min_case[i] = cur_max;
        cur_max--;
    }
    for (auto it:v)
    {
        int swaplen = it.second-it.first+1;
        for (int i = 0; i<swaplen/2; i++)
            swap(min_case[it.first+i],min_case[it.second-i]);
    }
    vprint(min_case, n);
 
 
    int cur_min = 1;
    for (int i = 0; i<n-1; i++)
    {
        if (s[i] == '>')
            cnt++;
        else
        {
            if (cnt>0)
            {
                v2.push_back({i+1,cnt+1});
            }
            cnt = 0;
        }
    }
    v2.push_back({n,cnt+1});
    for (int i = 0; i<v2.size(); i++)
    {
        pii p = v2[i];
        v2[i] = {p.first-p.second+1,p.first};
    }
    for (int i = 1; i<=n; i++)
    {
        max_case[i] = cur_min;
        cur_min++;
    }
    for (auto it:v2)
    {
        int swaplen = it.second-it.first+1;
        for (int i = 0; i<swaplen/2; i++)
            swap(max_case[it.first+i],max_case[it.second-i]);
    }
    vprint(max_case, n);
}
 
int32_t main()
{
    usecppio
    int t;
    cin >> t;
    while(t--) solve();
}

---

E. 1-Trees and Queries

백준에 많이 있는 트리와 쿼리 시리즈가 생각나는 문제 제목을 보고 바로 손절각을 재다가 (그런 문제는 처음 듣는 자료구조를 쓰는게 너무 많아서...) 일단 D까지 푼게 있으니 문제나 보려고 했는데 뭔가 바로 생각나는게 맞는것 같아서 그대로 코딩했다. 

어떤 트리에 새로운 간선 $x, y$ 를 추가한다고 할 때 (사이클이 생기게 될 것이다) $a$에서 출발하여 $b$ 를 $k$ 시간에 정확히 도착할 수 있는지를 빠르게 파악하고 싶다. 이때, 한 간선을 앞뒤로 왔다갔다 하면서 시간을 때워도 되지만 그 자리에 가만히 서 있는 것은 허용되지 않는다.

 

먼저, 트리에 간선 추가가 없다고 가정하고 이 문제를 풀어 보자. 임의의 점에 루트를 고정하고 나면 lca를 이용하여 트리에서 두 점을 오가는 가장 빠른 경로를 $O(\log n)$ 에 찾을 수 있으며, 가장 핵심적인 조건이 이때 점의 홀짝성 (짝수번만큼은 어떻게든 앞뒤를 오가며 남는 시간을 항상 다 때울 수 있다) 임을 알 수 있다. 즉, 시간을 다 때울 수 있는지 여부는 거리의 홀짝성에 의해 정해진다는 의미이다.

 

추가된 간선으로 인해 생기는 사이클의 길이가 짝수라면, 상황의 변화가 전혀 없게 된다. (앞뒤로 오가는 대신 사이클을 돌면서 시간을 때울 수 있지만, 의미가 없으므로) 예외적으로 추가된 간선으로 인해 더 빨리 갈 수 있는 경우만 처리해 주면 된다.

만약 추가된 간선으로 인해 생기는 사이클의 길이가 홀수라면, 원래는 패리티 때문에 때울 수 없었던 시간을 사이클을 돌면서 때울 수 있다. 이때 사이클이 있을 때의 최단경로는 사이클이 없을 때와 달라지므로, 이를 감안하여 케이스를 추가로 처리해야 한다. 

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
const bool debug = 1;
int n, m;
bool visited[101010];
int par[101010][21];
int d[101010];
int dist[101010];
vector <pii> graph[101010]; // {destination, weight}
void dfs(int here,int depth) // run dfs(root,0)
{
    visited[here] = true;
    d[here] = depth;
    for (auto there : graph[here])
    {
        if (visited[there.first])
            continue;
        dfs(there.first, depth + 1);
        par[there.first][0] = here;
    }
}
 
void precomputation()
{
    for (int i = 1; i<21; i++)
        for (int j = 1; j<=n; j++)
            par[j][i] = par[par[j][i-1]][i-1];
}
 
int lca(int x, int y)
{
    if (d[x]>d[y])
        swap(x,y);
    for (int i = 20; i>=0; i--)
        if (d[y]-d[x] >= (1<<i))
            y = par[y][i];
    if (x==y)
        return x;
    for (int i = 20; i>=0; i--)
    {
        if (par[x][i] != par[y][i])
        {
            x = par[x][i];
            y = par[y][i];
        }
    }
 
    int lca_point = par[x][0];
    return lca_point;
}
 
void tobedone()
{
    dfs(1,0);
    precomputation();
}
 
int distr[101010];
 
inline int treedist(int a, int b)
{
    return distr[a]+distr[b] - 2*(distr[lca(a,b)]);
}
 
bool check(int req_hang, int clen)
{
    if (req_hang%2==0) return true;
    if (clen%2==1)
    {
        if (req_hang>=clen)
            return true;
    }
    return false;
}
 
int32_t main()
{
    usecppio
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back({v, 1});
        graph[v].push_back({u, 1});
    }
    tobedone();
    memset(distr, -1, sizeof(distr));
    queue<int> q;
    q.push(1);
    distr[1] = 1;
    while (!q.empty())
    {
        int x;
        x = q.front();
        q.pop();
        for (auto it:graph[x])
        {
            if (distr[it.first] == -1)
            {
                q.push(it.first);
                distr[it.first] = distr[x] + it.second;
            }
        }
    }
    int query;
    cin >> query;
    while(query--)
    {
        int x, y, a, b, k;
        cin >> x >> y >> a >> b >> k;
        int ormindist = treedist(a, b);
        int cycle_len = treedist(x, y)+1;
        bool able = false;
        /* No riding cycle */
        if (k>=ormindist)
        {
            if ((k-ormindist)%2==0)
                able = true;
        }
        /* Riding cycle */
        int newmindist = INT_MAX;
        newmindist = min(newmindist, treedist(a, x)+1+treedist(y, b));
        newmindist = min(newmindist, treedist(a, y)+1+treedist(x, b));
        if (k >= newmindist)
        {
            if ((k-newmindist)%2==0)
                able = true;
            if ((k-cycle_len-newmindist)>=0)
                if ((k-cycle_len-newmindist)%2==0)
                    able = true;
        }
        cout << (able?"YES\n":"NO\n");
    }
 
}

---

오렌지 찍었으니까 이제 Div2 라운드에서 E, F들 중심으로 보면서 (어차피 Unrated인 동안에는 최대한 공부 효율이 좋으려면 지금은 잘 못 푸는 문제들을 많이 풀어야 하니까) 공부해야 할 것 같다. 가장 부족한 DP / 자구는 뭔가 계속 안 하고 있고... 2D세그, 2D펜윅, PST 같은 자료구조는 아직도 전혀 모르겠다. :(