Codeforces Round #693 (Div. 3)

A - Cards for Friends

Problem - A - Codeforces

\(w \times h\)크기의 종이가 있다.

현재 존재하는 종이 중 하나를 골라서 가로나 세로의 길이가 2로 나누어 떨어진다면 반으로 자를 수 있다.

 

이 종이를 잘라 \(n\)개 이상의 조각을 만들 수 있는지 알아내야 한다.

\(w, h\)각각의 소인수에 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; }
 
ll w, h, n;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> w >> h >> n;
        ll x = 1, y = 1;
        while (w % 2 == 0)
        {
            w /= 2;
            x *= 2;
        }
        while (h % 2 == 0)
        {
            h /= 2;
            y *= 2;
        }
 
        if (x * y >= n) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Fair Division

Problem - B - Codeforces

1그램짜리와 2그램짜리 사탕 여러개가 주어진다.

이 사탕을 두 그룹으로 나눠서 각 그룹이 같은 무게가 되도록 할 수 있는지 여부를 알아내야 한다.

 

2그램짜리 사탕을 최대한 비슷하게 나눈다음, 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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        int a = 0, b = 0;
        while (n--)
        {
            int x; cin >> x;
            if (x == 1) a++;
            else b++;
        }
 
        bool ans = false;
        if (b % 2 == 0)
        {
            if (a % 2 == 0) ans = true;
        }
        else
        {
            if (a >= 2 && a % 2 == 0) ans = true;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
     }
}

---

C - Long Jumps

Problem - C - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

이 배열의 임의의 인덱스 \(i\)를 골라서, 자신의 점수에 \(a_i\)를 더한 다음 현재 인덱스에 \(a_i\)를 더하자.

인덱스가 배열의 범위를 벗어날 때까지 반복할 때, 얻을 수 있는 최대 점수를 알아내야 한다.

 

간단한 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 n;
ll a[200001];
 
ll dp[200001];
 
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 >> a[i];
            dp[i] = 0;
        }
 
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] += a[i];
            ans = max(ans, dp[i]);
 
            if (i + a[i] < n)
            {
                dp[i + a[i]] = max(dp[i + a[i]], dp[i]);
            }
        }
 
        cout << ans << '\n';
     }
}

---

D - Even-Odd Game

Problem - D - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

두 사람이 이 배열로 게임을 한다.

 

선공은 이 배열에서 임의의 수를 하나 고른다.

그 수가 짝수라면 점수를 얻고, 홀수라면 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;
vector <ll> a, b;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        a.clear(), b.clear();
 
        for (int i = 0; i < n; i++)
        {
            ll x; cin >> x;
            if (x % 2 == 0) a.push_back(x);
            else b.push_back(x);
        }
 
        sort(a.rbegin(), a.rend());
        sort(b.rbegin(), b.rend());
 
        int aptr = 0, bptr = 0;
 
        ll asum = 0, bsum = 0;
 
        int turn = 0;
        while (aptr < a.size() || bptr < b.size())
        {
            ll ca = aptr < a.size() ? a[aptr] : 0;
            ll cb = bptr < b.size() ? b[bptr] : 0;
 
            if (turn == 0)
            {
                if (aptr < a.size())
                {
                    if (ca >= cb)
                    {
                        asum += a[aptr];
                        aptr++;
                    }
                    else bptr++;
                }
                else bptr++;
            }
            else
            {
                if (bptr < b.size())
                {
                    if (cb >= ca)
                    {
                        bsum += b[bptr];
                        bptr++;
                    }
                    else aptr++;
                }
                else aptr++;
            }
 
            turn = 1 - turn;
        }
 
        if (asum > bsum) cout << "Alice\n";
        else if (asum < bsum) cout << "Bob\n";
        else cout << "Tie\n";
    }
}

---

E - Correct Placement

Problem - E - Codeforces

\(n\)명의 사람이 있다.

각 사람은 직사각형 모양이고(!), 크기를 \(h_i \times w_i\)로 나타낼 수 있다.

 

각 \(i\)번째 사람에 대해, 다음 중 하나를 만족하는 사람의 인덱스 \(j\)를 구해야 한다.

1. \(h_i > h_j\) and \(w_i > w_j\)

2. \(h_i > w_j\) and \(w_i > h_j\)

 

그런 사람이 없다면 -1을 출력한다.

 

 

먼저 무조건 \(w < h\)이 되도록 하면 1번 조건에 대해서만 탐색하면 됨을 알 수 있다.

그 후 \(w\)순으로 정렬 한 다음, \(h\)를 set이나 세그트리 등으로 적절히 잘 저장하면,

위의 조건을 만족하는 사람의 인덱스를 알 수 있다.

 

#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 N = 200001;
const ll INF = 1e12;
 
int n;
vector <pair<pll, int> > x;
ll ans[N];
 
pll segTree[N * 4];
 
void update(int ptr, int l, int r, int i, pll val)
{
    if (i < l || r < i) return;
    if (l == r)
    {
        segTree[ptr] = min(segTree[ptr], val);
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, val);
 
    segTree[ptr] = min(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
pll getVal(int ptr, int l, int r, int i, int j)
{
    if (j < l || r < i) return { INF, -1 };
    if (i <= l && r <= j) return segTree[ptr];
 
    return min(getVal(ptr * 2, l, (l + r) / 2, i, j), getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j));
}
 
vector <ll> vh, vw;
int getIdx(vector <ll>& vec, ll val)
{
    return lower_bound(vec.begin(), vec.end(), val) - vec.begin();
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        x.clear();
        vh.clear(), vw.clear();
 
        fill(segTree, segTree + n * 4, pll(INF, -1));
 
        for (int i = 1; i <= n; i++)
        {
            ll h, w; cin >> h >> w;
            if (h > w) swap(h, w);
 
            x.push_back({ {h,w}, i });
            vh.push_back(h);
            vw.push_back(w);
 
            ans[i] = -1;
        }
 
        sort(vh.begin(), vh.end());
        vh.erase(unique(vh.begin(), vh.end()), vh.end());
        sort(vw.begin(), vw.end());
        vw.erase(unique(vw.begin(), vw.end()), vw.end());
 
        for (int i = 0; i < n; i++)
        {
            x[i].first.first = getIdx(vh, x[i].first.first);
            x[i].first.second = getIdx(vw, x[i].first.second);
        }
 
        sort(x.begin(), x.end());
 
        for (int i = 0; i < x.size();)
        {
            ll ch = x[i].first.first;
 
            int j = i;
            while (j + 1 < x.size() && x[j + 1].first.first == ch) j++;
 
            vector <pair<pll, int> > v;
            for (; i <= j; i++)
            {
                v.push_back(x[i]);
 
                pll res = getVal(1, 0, n - 1, 0, ch - 1);
                if (res.first < x[i].first.second)
                {
                    ans[x[i].second] = res.second;
                }
            }
 
            for (auto it : v)
            {
                update(1, 0, n - 1, it.first.first, pll(it.first.second, it.second));
            }
        }
 
        for (int i = 1; i <= n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

F - New Year's Puzzle

Problem - F - Codeforces

\(2 \times n\) 크기의 격자가 있다.

이 격자에 \(m\)개의 장애물이 있고, 이 장애물에는 타일을 놓을 수 없다.

 

이 격자를 \(2 \times 1\)크기의 타일로 채울 수 있는지 여부를 알아내야 한다.

 

 

장애물을 \(c\)가 증가하는 순으로 정렬하자.

1. 각각의 \(c\)에 대해서, 2개의 행 모두에 장애물이 없거나 있으면 무시한다.

2. 그렇지 않다면, 이 열에 있는 장애물과 바로 뒤에 있는 장애물이 쌍을 이뤄야 한다.

바로 뒤에 있는 장애물도 둘 중 1개의 행에만 있어야 한다.

이 장애물의 열의 인덱스 \(c_i\)와, 이 바로 뒤에 있는 장애물의 열의 인덱스 \(c_j\)를 비교하자.

    2-1. \(c_i\)와 \(c_j\)를 2로 나누었을 때 나머지가 같다면, 두 장애물은 다른 행에 위치해야 한다.

    2-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; }
 
ll n, m;
map <int, int> mp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        mp.clear();
 
        bool ans = true;
        for (int i = 0; i < m; i++)
        {
            int r, c; cin >> r >> c;
            mp[c] += (1 << r - 1);
        }
 
        for (auto it = mp.begin(); it != mp.end(); it++)
        {
            int c = it->first;
            int r = it->second;
 
            if (r == 3) continue;
 
            if (++it == mp.end())
            {
                ans = false;
                break;
            }
 
            int nc = it->first;
            int nr = it->second;
 
            if (c % 2 == nc % 2)
            {
                if (nr != 3 - r)
                {
                    ans = false;
                    break;
                }
            }
            else
            {
                if (nr != r)
                {
                    ans = false;
                    break;
                }
            }
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

G - Moving to the Capital

Problem - G - Codeforces

\(n\)개의 정점과 \(m\)개의 간선으로 이루어진 방향그래프가 주어진다.

1번 정점에서 각각의 정점으로의 거리를 \(d_i\)라고 하자.

 

각 정점에서 다음의 조건에 따라 다른 정점들로 이동할 수 있다.

\(i\)번 정점에서 \(j\)번 정점으로 간선이 존재할 때,

1. \(d_i < d_j\)라면 제약없이 이동할 수 있다.

2. \(d_i \ge d_j\)라면 단 한 번만 이동할 수 있다.

 

각 정점에서 시작해서 위의 조건으로 이동했을 때 거쳐갈 수 있는 모든 정점 \(v\)에 대해, \(d_v\)의 최소값을 각각 출력해야 한다.

 

 

각 정점을 2번 조건을 사용하지 않았을 때/사용했을 때 2가지로 나누자.

정점을 이렇게 분할하고 난 다음 조건에 맞게 이동할 수 있게 새로 구축한 그래프는 DAG이므로, 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; }
 
const int INF = 987654321;
 
int n, m;
vector <int> graph[200001];
 
int d[200001];
int dp[200001][2];
 
int solve(int v, int b)
{
    int& ret = dp[v][b];
    if (ret != -1) return ret;
 
    if (v == 1) return ret = 0;
 
    ret = d[v];
    for (int nv : graph[v])
    {
        if (d[v] < d[nv])
        {
            int res = solve(nv, b);
            ret = min(ret, res);
        }
        else if (b == 0)
        {
            int res = solve(nv, 1);
            ret = min(ret, res);
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            d[i] = INF;
            dp[i][0] = dp[i][1] = -1;
        }
 
        for (int i = 0; i < m; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
        }
 
        queue <int> q;
        d[1] = 0; q.push(1);
 
        while (!q.empty())
        {
            int v = q.front(); q.pop();
            for (int nv : graph[v])
            {
                if (d[nv] != INF) continue;
                d[nv] = d[v] + 1;
                q.push(nv);
            }
        }
 
        for (int i = 1; i <= n; i++)
        {
            int res = solve(i, 0);
            cout << res << ' ';
        }
 
        cout << '\n';
    }
}