Codeforces Round #652 (Div. 2)

A - FashionabLee

Problem - A - Codeforces

어떤 정다각형을 좌표평면 위에 놓았을 때, 이 정다각형을 회전시켜서 X축과 평행한 변과 Y축과 평행한 변이 동시에 있을 수 있다면

이 정다각형을 아름답다고 하자.

 

\(n\)이 주어지면, 정 \(n\)각형이 아름다운지 여부를 알아내야 한다.

 

\(n\)이 4로 나눠 떨어지면 이 정다각형은 아름답다.

 

#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; cin >> n;
        if (n % 4 == 0) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - AccurateLee

Problem - B - Codeforces

\(n\)길이의 이진 문자열이 주어진다.

이 문자열의 "10"이라는 부분 문자열이 있다면 두 문자 '0', '1'중 하나를 삭제할 수 있다.

 

위의 연산을 이용해 이 문자열의 길이를 최소화 해야 한다.

그런 문자열이 여러가지라면, 사전순으로 가장 앞서는 것을 찾아야 한다.

 

관찰을 통해 '1'로 시작해 '0'으로 끝나는 모든 문자열은 문자 하나로 압축될 수 있음을 알 수 있다.

따라서 위를 만족하는 제일 긴 문자열을 찾아 '0' 하나로 대체하면 된다.

 

#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;
string s;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s;
 
        int cnt0 = 0, cnt1 = 0;
 
        int st = 0;
        for (; st < s.size(); st++)
        {
            if (s[st] == '0') cnt0++;
            else break;
        }
 
        int ed = s.size() - 1;
        for (; ed >= 0; ed--)
        {
            if (s[ed] == '1') cnt1++;
            else break;
        }
 
        bool flag = false;
        if (st <= ed) flag = true;
 
        for (int i = 0; i < cnt0; i++) cout << 0;
        if (flag) cout << 0;
        for (int i = 0; i < cnt1; i++) cout << 1;
        cout << '\n';
    }
}

---

C - RationalLee

Problem - C - Codeforces

\(n\)개의 수를 가진 배열 \(a\)가 있다.

이 수들을 \(k\)명의 사람들에게 \(w_i\)개씩 나눠 주려고 한다.

 

어떤 사람의 행복도는 받은 수들 중 최소값과 최대값의 합이라고 했을 때,

모든 사람의 행복도의 합의 최대값을 알아내야 한다.

 

우선 \(k\)명의 사람들에게 가장 큰 \(k\)개의 수를 하나씩 나눠 주면 최대값의 합이 최대가 됨을 알 수 있다.

남은 수로 최소값을 최대화 해야 되는데, \(w_i\)가 가장 큰 사람 부터 시작해서 남은 수 중에 가장 작은 수 부터 차례로 나눠주면 된다.

 

#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;
ll a[200001];
int w[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];
        for (int i = 0; i < k; i++) cin >> w[i];
 
        sort(a, a + n);
        sort(w, w + k);
        reverse(w, w + k);
 
        ll ans = 0;
 
        int cnt = 0;
        for (int i = 0; i < k; i++)
        {
            if (w[i] == 1) break;
            ans += a[cnt];
            cnt += w[i] - 1;
        }
 
        reverse(w, w + k);
        for (int i = 0; i < k; i++)
        {
            if (w[i] == 1) ans += 2 * a[n - 1 - i];
            else ans += a[n - 1 - i];
        }
 
        cout << ans << '\n';
    }
}

---

D - TediousLee

Problem - D - Codeforces

정점 1개만으로 이루어진 트리가 있다.

이를 1단계라고 했을 때, \(n\)단계 트리는 다음과 같은 규칙으로 만든다.

 

\(n-1\)단계의 모든 정점에 대해서,

1. 이 정점의 자식이 0개라면 자식을 하나 추가한다.

2. 이 정점의 자식이 1개라면 자식을 2개 추가한다.

3. 이 정점의 자식이 1개보다 많다면 아무것도 하지 않는다.

 

하나의 부모와 그것에 연결된 3개의 자식 총 4개의 정점으로 이루어진 형태를 claw라고 하자.

 

초기에 모든 정점은 초록색으로 칠해져 있는데, 한 claw의 모든 정점이 초록색으로 칠해져 있다면 이 정점들을 모두 노란색으로 칠할 수 있다.

 

노란색으로 칠할 수 있는 정점의 개수의 최대값을 알아내야 한다.

 

먼저 관찰을 통해, 하나의 claw를 정점으로하고, 서로 다른 두 claw가 하나의 정점을 공유한다면 간선을 이어 만든 그래프는 원래 그래프와 동형임을 알 수 있다.

(\(n\)단계 claw그래프는 \(n-2\)단계 원래 그래프와 같다)

 

따라서 \(n\)이 주어지면, \(n-2\)단계 그래프에서 이웃한 정점을 둘 다 선택하지 않으면서 선택할 수 있는 최대 정점의 개수를 찾는 문제로 변환할 수 있다.

 

각 단계에서 고를 수 있는 최대 정점의 수 (\(dp_i\))와, 루트가 포함되는지 여부(\(root_i\))를 저장하자.

초기값은 다음과 같다. \(dp_1 = 1, dp_2 = 1, root_1 = 1, root_2 = 0\)

 

\(n\)단계 그래프는 루트 하나에 1개의 \(n-1\)단계 그래프와 2개의 \(n-2\)단계 그래프를 추가한 형태라고 생각할 수 있다.

따라서 우선 \(dp_n = dp_{n-1} + 2 \times dp_{n-2}\)라고 생각할 수 있다.

그런데 만약 \(root_{n-1} = 0\)이고 \(root_{n-2} = 0\)이면, 여기에 루트 하나를 더 선택할 수 있다.

 

그렇게 \(dp_n\)을 계산했으면, 하나의 claw에 포함된 정점의 수인 4를 곱하면 된다.

 

#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 ll MOD = 1e9 + 7;
ll ans[2000001];
int tmp[2000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    ans[3] = 1, ans[4] = 1;
    tmp[3] = 1;
 
    for (int i = 5; i <= 2000000; i++)
    {
        ans[i] = (ans[i - 1] + ans[i - 2] * 2) % MOD;
        if (tmp[i - 2] == 0 && tmp[i - 1] == 0)
        {
            tmp[i] = 1;
            ans[i] = (ans[i] + 1) % MOD;
        }
    }
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        cout << ans[n] * 4 % MOD << '\n';
    }
}

---

E - DeadLee

Problem - E - Codeforces

\(n\)개의 음식과 \(m\)명의 친구가 있다.

각 음식은 \(w_i\)개씩 남아있고,

각 친구들은 자신이 먹고싶어하는 음식 \(x,y\)가 있다.

 

이제 친구들을 1명씩 차례로 부른다.

각 친구는 현재 좋아하는 음식 \(x,y\)가 각각 있다면 1개씩 먹는다.

하지만 \(x,y\)중 먹을 수 있는 음식이 하나도 없다면, 대신 본인이 잡아먹힌다. !!

 

내가 잡아먹히지 않을 수 있는지 여부를 판별하고, 가능하다면 친구를 부르는 순서를 출력해야 한다.

 

각 음식에 대해 이 음식을 먹고 싶어하는 사람의 수를 \(in_i\)라고 하자.

만약 \(in_i \le w_i\)인 음식이 있다면, 원하는 사람들을 모두 먹일 수 있다.

그러면 이 사람들은 가장 마지막에 불러도 무조건 적어도 하나의 음식을 먹을 수 있음을 알 수 있다.

이 사람들을 모두 제외하고, 또 \(in_i \le w_i\)인 음식이 있는지 확인하는 방식으로 계속해 나가서 모든 사람이 음식을 먹을 수 있는지 확인하면 된다.

 

#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, m;
int w[100001];
 
int x[200001];
int y[200001];
vector <int> graph[100001];
int in[100001];
 
bool cache[200001];
queue <int> q;
vector <int> ans;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
 
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i];
        graph[x[i]].push_back(i);
        graph[y[i]].push_back(i);
        in[x[i]]++, in[y[i]]++;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (in[i] <= w[i]) q.push(i);
    }
 
    while (!q.empty())
    {
        int f = q.front(); q.pop();
 
        for (int h : graph[f])
        {
            if (cache[h]) continue;
            cache[h] = 1;
            ans.push_back(h);
 
            if(x[h] != f)
            {
                if (--in[x[h]] <= w[x[h]]) q.push(x[h]);
            }
            else
            {
                if (--in[y[h]] <= w[y[h]]) q.push(y[h]);
            }
        }
    }
 
    if (ans.size() < m)
    {
        cout << "DEAD\n";
        return 0;
    }
 
    cout << "ALIVE\n";
    reverse(ans.begin(), ans.end());
    for (int it : ans) cout << it << ' ';
}

---

F - BareLee

Problem - F - Codeforces

Lee와 Ice Bear가 게임을 하려고 한다.

게임은 \(t\)라운드로 진행되고, Lee가 먼저 시작한다.

 

각 라운드마다 칠판에 \(s_i\)가 쓰인채로 시작한다.

각 차례마다 플레이어는 칠판에 쓰인 수 \(a\)를 지우고, \(a+1\) 또는 \(2a\)를 대신 써 넣을 수 있다.

\(e_i\)보다 큰 수를 써넣는 플레이어가 현재 라운드에서 패배하고, 다음 라운드에서 선공이 된다.

 

맨 마지막 라운드를 이기는 사람이 최종 승리한다고 할 때,

Lee가 Ice Bear의 행동과 상관 없이 승리할 수 있는지, 또 패배할 수 있는지 여부를 알아내야 한다.

 

먼저, 각 라운드에서 선공이 승리 또는 패배할 수 있는지 여부를 계산해보자.

이를 각각 \(win_i, lose_i\)라고 할 것이다.

 

두 사람이 승리를 위해 게임을 한다고 가정하자.

라운드에서 승리하기 위해서는 내 차례에 \(e_i\)를 써 넣어야 함을 알 수 있다.

따라서 \(e_i\)가 홀수라면, 내 차례 때 쓰여진 수가 짝수면 무조건 승리, 홀수면 무조건 패배한다.

(현재 수가 짝수인 쪽은 1을 더하기만 하면 된다)

 

\(e_i\)가 짝수라면, 현재 쓰여진 수가 \(\frac{e_i}{2}\)보다 크다면 위와 같이 홀수면 승리, 짝수면 패배한다.

그렇지 않고 현재 쓰여진 수가 \(\lfloor \frac{e_i}{4} \rfloor\)보다 크다면, 무조건 승리한다. (2를 곱하면 된다)

위에 모두에 해당되지 않는다면, \(\lfloor \frac{e_i}{4} \rfloor\)를 써 넣는 쪽이 승리하게 된다. 재귀적으로 해결하면 된다.

 

다음으로는 패배를 위해 게임을 한다고 가정하자.

라운드에서 패배하기 위해서는, 내 차례에 \(e_i\)보다 큰 수를 써 넣어야 함을 알 수 있다.

따라서 \(s_i\)가 \(\lfloor \frac{e_i}{2} \rfloor\)보다 크다면, 무조건 패배한다. (2를 곱하면 된다)

그렇지 않다면, \(\lfloor \frac{e_i}{2} \rfloor\)를 써 넣는 쪽이 패배하게 된다. 이 역시 재귀적으로 해결하면 된다.

 

각 라운드 별로 선공이 승리/패배 할 수 있는지 여부를 계산했으니, 전체 게임에 대해서 계산해보자.

현재 라운드까지 봤을 때 Lee가 승리할 수 있는지 여부를 \(cw\), 패배할 수 있는지 여부를 \(cl\)이라고 하자.

초기에 Lee가 선공이므로 \(cw = 0, cl = 1\)이라고 할 수 있다.

 

라운드 \(i\)에서, \(cw = 0, cl = 1\)이라면, 정의에 의해 \(cw = win_i, cl = lose_i\)이다.

\(cl = 1, cw = 0\)이라면, \(cw = \neg win_i, cl = \neg lose_i\)이다.

그렇지 않고 만약 현재 \(cw = 1, cl = 1\)이라면, 앞으로의 라운드에 상관없이 전체 라운드의 승리 여부를 Lee가 고를 수 있다.

또 \(cw = 0, cl = 0\)이라면, 역시 앞으로의 라운드에 상관없이 전체 라운드의 승리 여부를 Lee가 고를 수 없다.

 

#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 win[100001], lose[100001];
 
int isWin(ll s, ll e)
{
    if (e % 2)
    {
        if (s % 2) return 0;
        else return 1;
    }
    else
    {
        if (s > e / 2)
        {
            if (s % 2) return 1;
            else return 0;
        }
        else if (s > e / 4) return 1;
        else return isWin(s, e / 4);
    }
}
 
int isLose(ll s, ll e)
{
    if (s > e / 2) return 1;
    return isWin(s, e / 2);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int cw = 0, cl = 1;
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll s, e; cin >> s >> e;
        win[i] = isWin(s, e);
        lose[i] = isLose(s, e);
 
        if (cw == cl) break;
        if (cl)
        {
            cw = win[i];
            cl = lose[i];
        }
        else
        {
            cw = 1 - win[i];
            cl = 1 - lose[i];
        }
    }
 
    cout << cw << ' ' << cl;
}