Codeforces Round #703 (Div. 2)

A - Shifting Stacks

Problem - A - Codeforces

\(n\)묶음의 블록이 있다. 각각의 묶음에는 \(h_i\)만큼의 벽돌이 있다.

 

\(i\)번째 묶음에서 (블록이 1개이상 존재한다면) 블록 하나를 \(i+1\)번째 묶음으로 옮기는 연산을 할 수 있을 때,

블록의 개수가 오름차순이 되도록 할 수 있는지 알아내야 한다.

 

직접 시뮬레이션 하자.

\(i\)번째 묶음에 \(i\)개의 블록만을 놔두고 나머지는 전부 다음 묶음으로 옮기면 된다. (0-index)

 

#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;
ll h[105];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        memset(h, 0, sizeof h);
 
        bool ans = true;
 
        for (int i = 0; i < n; i++)
        {
            ll a; cin >> a;
            h[i] += a;
            if (h[i] < i) ans = false;
 
            h[i + 1] += h[i] - i;
            h[i] = i;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Eastern Exhibition

Problem - B - Codeforces

좌표평면 위에 \(n\)개의 점이 있다.

이 각각의 점까지의 맨해튼 거리의 합이 최소가 되는 점의 개수를 출력하면 된다.

 

일단 x축과 y축을 나눠 생각할 수 있다는 사실을 알 수 있다.

좌표를 정렬하고 나서 잘 생각해보면 \(n\)이 홀수일 때는 조건을 만족하는 점이 1개이고,

짝수일 때는 중간 점 2개 사이에 있는 모든 점이라는 사실을 알 수 있다.

 

x축과 y축에 대해 각각 구한다음 곱하면 된다.

 

#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;
ll x[1001], y[1001];
 
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 >> x[i] >> y[i];
 
        if (n % 2)
        {
            cout << "1\n";
            continue;
        }
 
        sort(x, x + n);
        sort(y, y + n);
 
        ll dx = x[n / 2] - x[n / 2 - 1] + 1;
        ll dy = y[n / 2] - y[n / 2 - 1] + 1;
 
        cout << dx * dy << '\n';
    }
}

---

C - Guessing the Greatest (hard version)

Problem - C2 - Codeforces

\(n\)개의 서로 다른 수로 이루어진 배열 \(a\)가 주어진다.

 

임의의 구간 \([l, r]\)에 대해, 2번째로 큰 수가 있는 위치를 알 수 있는 쿼리를 최대 20번 사용할 수 있을 때,

가장 큰 수가 있는 위치를 알아내야 한다.

 

전체 구간에서 2번째로 큰 수가 있는 위치를 쿼리로 알 수 있다.

이 위치 \(c\)에서 반지름이 \(r\)인 구간에 대해 쿼리를 날렸을 때 (\([c-r, c+r]\)),

이 구간에서도 2번째로 큰 수가 \(c\)에 있다면 이 구간 안에 가장 큰 수가 존재하며, 없다면 존재하지 않는다.

 

따라서 반지름의 크기에 대해 이분탐색을 하면 가장 큰 수의 위치가 두 군데로 좁혀지게 된다.

둘 중 어디인지 한번의 쿼리로 찾으면 된다.

 

#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 query(int l, int r)
{
    if (l >= r) return 0;
    cout << "? " << l << ' ' << r << endl;
    int res; cin >> res;
    return res;
}
 
int main()
{
    cin >> n;
 
    int c = query(1, n);
 
    int l = 0, r = n;
 
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        int res = query(max(1, c - m), min(n, c + m));
 
        if (res == c) r = m;
        else l = m;
    }
 
    if (query(max(1, c - r), c) == c) cout << "! " << max(1, c - r) << endl;
    else cout << "! " << min(n, c + r) << endl;
}

---

D - Max Median

Problem - D - Codeforces

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

이 배열의 길이 \(k\)이상의 모든 부분배열에 대해, 중간값의 최대값을 알아내야 한다.

 

어떤 수 \(x\)가 고정되어 있을 때, \(x\)보다 크거나 같은 수가 답이 될 수 있는지 알 수 있다.

\(a\)에서 \(x\)보다 크거나 같은 수를 1로, 작은 수를 -1로 치환하자.

이 배열에서 길이가 \(k\)이상인 부분배열의 합이 0보다 클 수 있다면, 중간값이 \(x\)보다 크거나 같을 수 있다는 뜻임을 알 수 있다.

 

이 작업은 \(O(n)\)에 할 수 있고, \(x\)에 대해 이분탐색을 함으로써 가장 큰 \(x\)를 찾을 수 있다.

 

#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 psum[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    int l = 1, r = n + 1;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
 
        bool flag = false;
 
        int cmin = 0;
        for (int i = 1; i <= k; i++)
        {
            if (a[i] >= m) psum[i] = psum[i - 1] + 1;
            else psum[i] = psum[i - 1] - 1;
        }
 
        if (psum[k] > 0) flag = true;
        for (int i = k + 1; i <= n; i++)
        {
            if (a[i] >= m) psum[i] = psum[i - 1] + 1;
            else psum[i] = psum[i - 1] - 1;
            cmin = min(cmin, psum[i - k]);
 
            if (psum[i] - cmin > 0) flag = true;
        }
 
        if (flag) l = m;
        else r = m;
    }
 
    cout << l;
}

---

E - Paired Payment

Problem - E - Codeforces

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

 

이 그래프에서 정점 사이의 거리는 다음과 같이 정해진다.

 

1. 한번에 2개의 이어진 간선을 이용해야 한다. (a->b->c 등)

2. 이 때 a와 c사이의 거리는 \((w_{ab}+w_{bc})^2\)이다.

 

1번 정점에서 나머지 정점까지의 최단거리를 알아내야 한다.

 

각 정점을 첫 번째 간선을 지났을 때의 최단거리와 두 번째 간선을 지난 후의 최단거리로 분할할 수 있다.

이 때 첫 번째 간선을 지났을 때의 최단거리는 이전에 이용한 간선의 가중치에 따라 다르게 관리해야 함을 알 수 있다.

가중치가 최대 50이므로, 한 정점을 총 51개로 분할해 다익스트라를 돌리면 된다.

 

#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 INF = 1e18;
 
int n, m;
vector <pll> graph[100001];
ll dist[51][100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i <= 50; i++) for (int j = 1; j <= n; j++)
        dist[i][j] = INF;
 
    for (int i = 0; i < m; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        graph[u].push_back({ v,w });
        graph[v].push_back({ u,w });
    }
 
    priority_queue<pair<ll, pii> > pq;
    dist[0][1] = 0; pq.push({ 0,{0,1} });
 
    while (!pq.empty())
    {
        auto it = pq.top(); pq.pop();
        int k = it.second.first;
        int v = it.second.second;
        ll cd = -it.first;
 
        if (cd > dist[k][v]) continue;
 
        for (auto to : graph[v])
        {
            int nv = to.first;
            ll d = to.second;
            int nk = (!k ? d : 0);
            ll nd = (!k ? 0 : (k + d) * (k + d));
 
            if (dist[nk][nv] > cd + nd)
            {
                dist[nk][nv] = cd + nd;
                pq.push({ -dist[nk][nv],{nk,nv} });
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (dist[0][i] == INF) cout << "-1 ";
        else cout << dist[0][i] << ' ';
    }
}

---

F - Pairs of Paths

Problem - F - Codeforces

추가 예정