Codeforces Round #637 (Div. 1, Div. 2)

와!

A - Nastya and Rice

Problem - A - Codeforces

\(n\)개의 쌀알이 있다.

 

쌀알 하나의 무게는 최소 \(a-b\) 최대 \(a+b\)이고,

쌀알 전체의 무게는 최소 \(c-d\) 최대 \(c+d\)이다.

 

\(n,a,b,c,d\)가 주어질 때, 이 값들이 올바른지 알아내야 한다.

 

쌀알 전체의 무게를 \(a\)와 \(b\)를 이용해 나타내면

\([n\cdot (a-b), n\cdot (a+b)]\)가 된다.

이 범위가 \([c-d, c+d]\)와 한 점이라도 겹치면 올바른 값이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
 
        if ((a - b) * n <= c + d && (a + b) * n >= c - d) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

B - Nastya and Door

Problem - B - Codeforces

길이가 \(k\)인 문짝이 있다.

이 문짝을 \(n\)길이의 산 \(a\)에 던져 부숴버리려고 한다.

 

산의 어떤 구간 \([l,r]\)에 대해 \(l \lt i \lt r\), \(a_{i-1} \lt a_i\), \(a_i \lt a_{i+1}\)를 만족한다면 \(a_i\)를 산봉우리라고 한다.

산에 문짝을 던졌을 때, 문짝은 문짝이 덮는 구간에 있는 산봉우리의 개수만큼 쪼개지게 된다.

 

문짝이 쪼개져 나올 수 있는 최대 조각 수를 구해야 한다.

 

어떤 점 \(a_i\)가 산봉우리인지는 \(O(1)\)에 알 수 있다.

그 후 산봉우리의 누적합을 구하면, 어떤 구간내에 존재하는 산봉우리의 개수도 \(O(1)\)에 구할 수 있게 된다.

 

가능한 모든 경우에 대해 산봉우리의 누적합의 최대값을 구하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, k;
int a[200001];
int peak[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            peak[i] = 0;
        }
        for (int i = 1; i < n - 1; i++)
        {
            if (a[i] > a[i - 1] && a[i] > a[i + 1]) peak[i] = 1;
        }
        for (int i = 1; i < n; i++) peak[i] += peak[i - 1];
        
        int ans = 0;
        int l = 0;
        for (int i = 0; i <= n - k; i++)
        {
            int res = peak[k + i - 2] - peak[i] + 1;
            if (res > ans) ans = res, l = i + 1;
        }
 
        cout << ans << ' ' << l << '\n';
    }
}

---

A - Nastya and Strange Generator

Problem - A - Codeforces

순열을 만드는 다음과 같은 알고리즘이 주어진다.

 

각 \(i\)번째 단계마다, (\(1 \le i \le n\))

1. \(1\)이상 \(n\)이하의 모든 \(j\)에 대하여, \(r_j\)를 계산한다. \(r_j\)는 \(j\)이상 \(n\)이하의 모든 인덱스에 대하여, 아직 수를 써넣지 않은 가장 작은 인덱스이다. (값이 정의되지 않을 수도 있다)

2. \(1\)이상 \(n\)이하의 모든 \(t\)에 대하여, \(count_t\)를 계산한다. \(count_t\)는 \(1 \le j \le n\)에 대하여 \(r_j = t\)인 \(j\)의 개수이다.

3. \(count_t\)의 값이 가장 큰 \(t\)값 중에 아무거나 골라 \(t\)번째 인덱스에 \(i\)를 써넣는다.

 

주어진 순열이 주어질 때, 위의 알고리즘으로 나올 수 있는지 여부를 알아내야 한다.

 

알고리즘이 복잡하게 쓰여져 있지만, 관찰을 잘 해보면 다음과 같은 점을 알아낼 수 있다.

1. 어떤 중간 지점부터 수를 써넣기 시작했다면, 그 다음 칸이 마지막 칸이거나 수가 쓰여있을 때까지 오른쪽으로 차례대로 수를 채워야 한다.

2. 마지막으로 쓴 칸 다음 칸이 마지막 칸이거나 수가 쓰여 있다면, 다음 시작점은 마음대로 정할 수 있다.

 

순열의 각 숫자의 인덱스를 확인해서 위의 규칙을 만족하는지 확인하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int p[100001];
int idx[100001];
bool isUsed[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> p[i];
            idx[p[i]] = i;
            isUsed[i] = 0;
        }
 
        isUsed[n] = 1;
 
        bool isValid = true;
        int lastIdx = n - 1;
        for (int i = 1; i <= n; i++)
        {
            int cidx = idx[i];
            if (isUsed[lastIdx + 1] || cidx == lastIdx + 1)
            {
                lastIdx = cidx;
                isUsed[cidx] = 1;
            }
            else
            {
                isValid = false;
                break;
            }
        }
 
        if (isValid) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

B - Nastya and Scoreboard

Problem - B - Codeforces

\(n\)개의 7세그먼트 디스플레이가 주어진다.

 

이 디스플레이의 초기에 켜져있는 세그먼트가 각각 주어진다.

여기에서 정확하게 \(k\)개의 세그먼트를 더 켤 수 있을 때, 만들 수 있는 수의 최대값을 알아내야 한다.

 

초기 디스플레이에 대해, 0부터 9까지 수를 만드는데 추가로 켜야하는 디스플레이의 수 (또는 불가능한지 여부)를 미리 계산할 수 있다.

이 값을 \(pl_{i, num}\)이라고 하자. (i번째 디스플레이로 num을 만드는데 필요한 세그먼트의 수)

 

다음과 같은 DP식을 정의하자.

\(DP(i, k) :\) i번째 세그먼트를 보고 있고, 켤 수 있는 세그먼트가 \(k\)개 남았을 때, 올바른 수를 만들어 낼 수 있는가? (true or false)

 

그럼 다음과 같은 점화식을 얻을 수 있다.

\(DP(i, k) = DP(i+1, k-pl_{i, 0}) \lor DP(i+1, k-pl_{i, 1}) \lor \cdots \lor DP(i+1, k-pl_{i, 9})\)

 

DP테이블을 채운 다음, 맨 앞 디스플레이부터 만들 수 있는 가장 큰 숫자를 그리디하게 선택하면 답이 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int bs[10] = { 119,36,93,109,46,107,123,37,127,111 };
int count_bit(int x)
{
    int res = 0;
    for (int i = 0; i < 7; i++)
    {
        if (x & (1 << i)) res++;
    }
 
    return res;
}
 
int n, k;
int dig[2001];
int pl[2001][10];
 
string ans;
int dp[2001][2001];
int solve(int idx, int rm)
{
    if (idx == n && rm == 0) return 1;
 
    int& ret = dp[idx][rm];
    if (ret != -1) return ret;
 
    for (int i = 9; i >= 0; i--)
    {
        if (pl[idx][i] == -1 || rm < pl[idx][i]) continue;
 
        ans += (char)('0' + i);
        if (solve(idx + 1, rm - pl[idx][i])) return ret = 1;
        ans.pop_back();
    }
 
    return ret = 0;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(pl, -1, sizeof pl);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        string s; cin >> s;
        for (int j = 0; j < 7; j++)
        {
            dig[i] += ((s[j] - '0') << j);
        }
 
        for (int j = 0; j < 10; j++)
        {
            if ((bs[j] & dig[i]) == dig[i])
            {
                int cnt = count_bit(bs[j] & (~dig[i]));
                pl[i][j] = cnt;
            }
        }
    }
 
    memset(dp, -1, sizeof dp);
 
    if (solve(0, k)) cout << ans;
    else cout << -1;
}

---

C - Nastya and Unexpected Guest

Problem - C - Codeforces

\(n\)길이의 도로가 있다. 이 도로에는 \(m\)개의 안전지대가 있다.

이 도로에는 신호등이 있고, 초록불이 \(g\)초 켜진 다음, 빨간불이 \(r\)초 켜진다.

 

이 도로의 위치 \(0\)에서 시작해 위치 \(n\)까지 이동하려고 하는데, 다음과 같은 규칙으로 이동해야 한다.

1. 초록불일 때는 무조건 1초에 1만큼 이동해야 한다. 이동하는 위치가 \([0,n]\)을 벗어날 수는 없다.

2. 이동하는 방향을 바꾸는 것은 안전지대에서만 할 수 있다.

3. 빨간불이 켜지는 순간에는 안전지대에 있어야 한다. 빨간불일 때는 이동할 수 없다.

 

이 때, 위치 \(n\)까지 이동하는데 걸리는 최소 시간을 구해야 한다.

 

현재 \(i\)번째 안전지대에 있고, 초록불이 된지 \(j\)초가 지난 상황 \((i, j)\)을 정점으로 하는 그래프를 생각해보자.

그러면 문제를 정점 \((0,0)\)에서 출발해서 \((m-1, x)\)까지 이동하는데 최단거리를 구하는 문제로 생각할 수 있게 된다.

 

가장 쉽게 생각할 수 있는 방법은 다익스트라이다.

먼저 정점의 개수를 생각해보면 최대 \(m \times g\)개이다. \(m\)이 최대 \(10^4\)이고, \(g\)가 최대 \(10^3\)이다.

간선은 정점당 최대 2개 있을 수 있다.

따라서 총 시간복잡도는 \(O(mg\log (mg))\)인데, 1초안에 작동하기에는 매우 애매한 숫자이고, 실제로 시간초과를 받는다.

 

시간 줄이기 위해 사용할 수 있는 다른 방법은 0-1 BFS가 있다.

어떤 정점에서 다른 정점으로 이동한 직후 빨간 불이 되었다면, 그 사이의 거리를 1이라고 하자. 그렇지 않다면 거리는 0이다.

 

그러면 정점 \((m-1, x)\)까지 저장되어 있는 거리는 초록불-빨간불 사이클을 지난 횟수이므로, \((r+g)\)를 곱하고 \(x\)를 더하면 총 걸린 시간을 쉽게 계산할 수 있다.

이 방법으로 시간복잡도는 \(O(mg)\)로, 충분히 시간안에 들어올 수 있게 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int INF = numeric_limits<int>::max();
int n, m;
int d[10001];
int dist[10001][1001];
int g, r;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(dist, -1, sizeof dist);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> d[i];
    cin >> g >> r;
 
    sort(d, d + m);
 
    deque <pii> dq;
    dist[0][0] = 0;
    dq.push_back({ 0,0 });
 
    while (!dq.empty())
    {
        int idx = dq.front().first;
        int tm = dq.front().second;
        dq.pop_front();
 
        //cout << "IDX, TM: " << idx << ' ' << tm << "\n";
        if (tm < 0)
        {
            int stop_here = 0;
        }
 
        int r_tm = g - tm;
        
        int nidx = idx + 1;
        int sub = d[nidx] - d[idx];
        int ntm = (tm + sub) % g;
 
        if (idx < m - 1)
        {
            if (sub <= r_tm && dist[nidx][ntm] == -1)
            {
                if (ntm == 0)
                {
                    dist[nidx][ntm] = dist[idx][tm] + 1;
                    dq.push_back({ nidx, ntm });
                }
                else
                {
                    dist[nidx][ntm] = dist[idx][tm];
                    dq.push_front({ nidx, ntm });
                }
            }
        }        
 
        if (idx > 0)
        {
            nidx = idx - 1;
            sub = d[idx] - d[nidx];
            ntm = (tm + sub) % g;
 
            if (sub <= r_tm && dist[nidx][ntm] == -1)
            {
                if (ntm == 0)
                {
                    dist[nidx][ntm] = dist[idx][tm] + 1;
                    dq.push_back({ nidx, ntm });
                }
                else
                {
                    dist[nidx][ntm] = dist[idx][tm];
                    dq.push_front({ nidx, ntm });
                }
            }
        }
    }
 
    int ans = INF;
    for (int i = 0; i < g; i++)
    {
        if (dist[m - 1][i] != -1)
        {
            int res = dist[m - 1][i] * (r + g) + i;
            if (i == 0) res -= r;
            ans = min(ans, res);
        }
    }
 
    if (ans == INF) ans = -1;
    cout << ans;
}

---

D - Nastya and Time Machine

Problem - D - Codeforces

정점이 \(n\)개인 트리가 주어진다.

이 트리의 루트(1)에서 시작해 모든 정점을 방문한 다음 다시 루트로 돌아오려고 한다.
어떤 정점에서 다른 정점까지 이동하는데는 1의 시간이 걸린다.
이동하는 중에, 어떤 정점에서 타임머신을 사용해 임의의 과거의 시간으로 시간이동을 할 수 있다.
대신 어떤 정점에서, 같은 시간대에 두 번 이상 존재하게 되도록 이동할 수는 없다.

이 때 각 정점에 있는 시간대의 최대값이 최소가 되도록 이동하는 경로를 알아내야 한다.

먼저 어떤 정점 \(v\)의 직계 자식이 \(child_v\)개라고 하자.

직계 자식에서 이 정점으로 다시 돌아오는 횟수가 \(child_v\)회이므로, 이 정점에서 가능한 시간대의 최솟값은 \(child_v+1\)임을 알 수 있다.
그렇다고 정확하게 \(child_v+1\)개의 시간대로 문제를 해결할 수 있는가 하면 그렇지 않다.

현재 정점의 부모로 되돌아 갈 때, 현재 정점의 시간대는 \(child_v\)일 것이므로 이동 후 부모의 시간대는 \(child_v+1\)가 될 것인데, 많은 상황에서 이것은 최적이 아님을 관찰로써 알 수 있다.

즉, 부모 정점으로 돌아가기 전에 적어도 한번의 시간이동을 한 후에 부모한테 돌아가는 것이 최적임으로 한번의 시간이동을 포함해 루트를 제외한 정점은 최소 \(child_v+2\)번의 시간대를 가지게 됨을 알 수 있다.

 

따라서 답의 하한은 모든 정점 \(v\)에 대해 \(child_v+2\)의 최댓값 (루트의 경우는 \(child_v+1\))이고, 이 하한에 맞도록 답을 만드는 것이 언제나 가능함도 알 수 있다.

 

남은 것은 구현이다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
vector <int> graph[100001];
vector <int> tree[100001];
 
void pre_DFS(int v, int p)
{
    for (auto nv : graph[v])
    {
        if (nv == p) continue;
        tree[v].push_back(nv);
        pre_DFS(nv, v);
    }
}
 
vector <pii> ans;
int DFS(int v, int p, int tm)
{
    ans.push_back({ v,tm });
 
    int ctm = tm;
 
    int rm = tm - 1;
 
    for (int i = 0; i < tree[v].size(); i++)
    {
        int nv = tree[v][i];
 
        int bk = tree[v].size() - i;
        if (bk <= rm)
        {
            if (ctm != rm - bk)
            {
                ctm = rm - bk;
                ans.push_back({ v, ctm });
            }
            
            ctm = DFS(nv, v, ctm + 1);
        }
        else
        {
            ctm = DFS(nv, v, ctm + 1);
        }
 
        ans.push_back({ v, ctm });
    }
 
    if (ctm != tm - 1)
    {
        ctm = tm - 1;
        if (v != 1) ans.push_back({ v,ctm });
    }
 
    return ctm + 1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    pre_DFS(1, 0);
    DFS(1, 0, 0);
 
    cout << ans.size() << '\n';
    for (auto it : ans) cout << it.first << ' ' << it.second << '\n';
}

---

E - Nastya and Bees

Problem - E - Codeforces

추가 예정

---

F - Nastya and CBS

Problem - F - Codeforces

추가 예정