Codeforces Round #645 (Div. 2)

다시 돌아왔다!

A - Park Lighting

Problem - A - Codeforces

\(n \times m\)크기의 공원이 있다.

한 개의 랜턴을 이용해 \(1 \times 2\)크기의 구역을 밝힐수 있다고 할 때, 공원을 모두 밝히기 위해 필요한 랜턴의 최소 개수를 구해야 한다.

 

먼저 \(nm\)이 짝수면, 답이 \(\frac{nm}{2}\)임은 자명하다.

\(nm\)이 홀수라면, 귀퉁이 한 칸을 제외한 나머지 구역을 \(\frac{nm-1}{2}\)개의 랜턴으로 밝힐 수 있고, 하나의 랜턴을 더 사용해서 남은 한 칸을 밝히면 된다.

 

따라서 답은 \(\lfloor \frac{nm+1}{2} \rfloor\)이다.

 

#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, m; cin >> n >> m;
        cout << (n * m + 1) / 2 << '\n';
    }
}

---

B - Maria Breaks the Self-isolation

Problem - B - Codeforces

\(n\)명의 사람을 집에 초대하려고 한다.

\(i\)번째 사람은 본인이 도착했을 때 집주인을 포함해서 본인보다 빠르거나 같은 시간에 온 사람이 \(a_i\)명 이상일 수 있으면 초대에 응한다.

 

이 때 집에 있을 수 있는 최대 인원을 구해야 한다.

 

먼저 \(a_i < a_j\)인 \(i, j\)에 대해, \(j\)번째 사람을 초대할 수 있다면 \(i\)번째 사람도 무조건 초대할 수 있음을 알 수 있다.

따라서 \(a\)를 정렬한 다음, \(i \ge a_i\)를 만족하는 가장 큰 \(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;
int a[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 >> a[i];
        sort(a, a + n);
 
        int r = n - 1;
        while (r >= 0)
        {
            if (r + 1 >= a[r]) break;
            r--;
        }
 
        cout << r + 2 << '\n';
    }
}

---

C - Celex Update

Problem - C - Codeforces

격자에 그림에 주어진 규칙대로 수를 써 넣는다.

어떤 칸 \((x,y)\)에서 \((x+1,y)\) 또는 \((x,y+1)\)로 이동할 수 있다고 하자.

\((x_1,y_1)\)에서 \((x_2,y_2)\)로 이동하는데 경로에 써있는 수의 합이 될 수 있는 수의 가짓수를 구해야 한다.

 

시작해서 오른쪽으로만 이동한 다음 아래쪽으로만 이동하면 이동경로의 수의 합이 최소값이고,

아래쪽으로만 이동한 다음 오른쪽으로만 이동하면 이동경로의 수의 합이 최대값이 될 것이다.

 

여기에서 이동 경로를 적절히 조정함으로써 최소값과 최대값 사이의 값을 모두 만들어낼 수 있음을 관찰로 알 수 있다.

임의의 이동경로와 합이 최소가 되는 이동경로로 만들어지는 다각형의 넓이가 이 이동경로와 최소값의 차이인데, 이 다각형의 넓이를 원하는 만큼 조정할 수 있기 때문에 가능하다.

 

따라서 \(ans_{max}-ans_{min}+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--)
    {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
 
        ll mn = min(x2 - x1, y2 - y1);
        ll mx = max(x2 - x1, y2 - y1);
 
        ll ans = (mn - 1) * mn;
        ans += (mx - mn + 1) * mn;
 
        cout << ans + 1 << '\n';
    }
}

---

D - The Best Vacation

Problem - D - Codeforces

1년이 \(n\)개의 달로 이루어져 있고, 각각의 달은 \(d_i\)개의 날로 이루어져 있는 이상한 곳이 있다.

 

정확히 \(x\)개의 연속된 날을 고르려고 하는데, 각각의 날이 달의 \(j\)번째 날이라면 \(j\)의 점수를 얻는다.

얻을 수 있는 가장 큰 점수를 구해야 한다.

 

먼저 답이 존재한다면, 맨 마지막 날이 각 달의 마지막 날이 되는 것이 최적이다.

 

귀류법으로 증명할 수 있다.

만약 답이 되도록 선택한 날들이 어떤 날 \(d\)에서 끝난다고 하자.

이 날들을 전체적으로 1일씩 뒤로 옮기면 전체 합이 줄어들 것이다.

마지막의 다음 날의 점수는 \(d+1\)이므로, 첫 날의 점수는 \(d+1\)보다 커야 한다.

그런데 첫 칸의 점수가 \(d+1\)보다 크다면, 첫 칸의 이전 날의 점수는 \(d\)보다 크다는 뜻인데,

그렇다면 선택한 날을 하루씩 전날로 옮기면 더 점수가 크게 되므로, 모순이다.

 

따라서 \(n\)개의 달에 대해 각각의 맨 마지막 날을 끝 날로 설정하고, 부분 합을 이용해 이분탐색을 하면 답을 \(O(n\log n)\)에 알아낼 수 있다.

 

#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, x;
ll d[400001];
ll psum[400001];
ll ss[400001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> x;
    for (int i = n; i > 0; i--) cin >> d[i], d[n + i] = d[i];
    for (int i = 1; i <= 2 * n; i++)
    {
        psum[i] = psum[i - 1] + d[i];
        ss[i] = ss[i - 1] + (d[i] * (d[i] + 1) / 2);
    }
 
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = i - 1, r = 2 * n;
        while (l + 1 < r)
        {
            int m = (l + r) / 2;
            ll res = psum[m] - psum[i - 1];
 
            if (res <= x) l = m;
            else r = m;
        }
 
        ll rm = x - (psum[l] - psum[i - 1]);
 
        ll res = ss[l] - ss[i - 1];
 
        ll t1 = d[l + 1];
        ll t2 = d[l + 1] - rm;
        
        res += t1 * (t1 + 1) / 2 - t2 * (t2 + 1) / 2;
 
        ans = max(ans, res);
    }
 
    cout << ans;
}

---

E - Are You Fired?

Problem - E - Codeforces

어떤 회사의 수익 현황이 주어진다.

첫 \(\lceil \frac n2 \rceil\)개의 날의 수익은 \(a_i\)이고,

다음 \(\lfloor \frac n2 \rfloor\)개의 날의 수익은 \(x\)로 일정하다.

 

전체적으로 수익이 좋아 보이기 만들기 위해, 연속된 \(k\)개의 수익을 합친 값들을 대신 발표하려고 한다.

\(k\)를 임의로 골랐을 때, 모든 값이 0보다 크도록 만드는 것이 가능한지 알아내야 한다.

가능하다면, 가능한 \(k\)를 아무거나 출력한다.

 

답이 존재한다면, \(\frac n2\)이상의 답도 무조건 존재한다.

만약 답이 \(k \lt \frac n2\)라면 \(k\)의 배수도 무조건 답이 되는데, \(k\)의 배수를 적당히 조절함으로써 \(\frac n2\)이상의 값이 되도록 만들 수 있기 때문이다.

 

먼저 답이 \(n\)이라고 가정하자.

\(a_i\)의 부분합을 구해놓고 이를 \(psum_i\)라고 한다면,

\(psum_0 \lt psum_n\)이 만족해야 하므로, \(psum_0 - psum_n \lt 0\)이어야 한다.

 

답이 \(n-1\)이라면?

\((psum_0 \lt psum_{n-1}) \land (psum_1 \lt psum_n)\)이 만족해야 하므로,
\((psum_0 - psum_{n-1} \lt 0) \land (psum_1 - psum_n \lt 0)\)이어야 한다.

 

두 식의 첫 항을 살펴보자. \(psum_0 - psum_n\)와 \(psum_0 - psum_{n-1}\)의 차이는 \(x\)이다.

따라서 일반적으로 답이 \(n-k\)인 경우를 계산하고 있다면, \(psum_k\)에 \(psum_n\)을 빼고,

\(psum_0 \cdots psum_{k-1}\)에 \(x\)를 더하면 됨을 알 수 있다.

 

현재 계산하는 답이 유효한지는 이 값들의 최대값이 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; }
 
const int N = 500001;
const ll INF = 987654321987654321;
 
ll n, x;
ll a[N];
ll psum[N];
 
ll segTree[N * 4];
ll lazy[N * 4];
 
void setLazy(int ptr, int l, int r)
{
    ll val = lazy[ptr];
    lazy[ptr] = 0;
 
    segTree[ptr] += val;
    if (l != r)
    {
        lazy[ptr * 2] += val;
        lazy[ptr * 2 + 1] += val;
    }
}
 
void update(int ptr, int l, int r, int i, int j, ll val)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (l > j || r < i) return;
    if (i <= l && r <= j)
    {
        segTree[ptr] += val;
        if (l != r)
        {
            lazy[ptr * 2] += val;
            lazy[ptr * 2 + 1] += val;
        }
        return;
    }
 
    update(ptr * 2, l, (l + r) / 2, i, j, val);
    update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j, val);
 
    segTree[ptr] = max(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
 
ll getVal(int ptr, int l, int r, int i, int j)
{
    if (lazy[ptr]) setLazy(ptr, l, r);
 
    if (l > j || r < i) return -INF;
    if (i <= l && r <= j) return segTree[ptr];
 
    return max(
        getVal(ptr * 2, l, (l + r) / 2, i, j),
        getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j)
    );
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    ll m = (n + 1) / 2;
 
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
 
    cin >> x;
 
    ll sum = psum[m] + x * (n / 2);
    //if (sum > 0)
    //{
    //    cout << n;
    //    return 0;
    //}
 
    for (int i = 0; i <= m; i++)
    {
        update(1, 0, m, i, i, psum[i]);
    }
 
    for (int i = 0; i <= n / 2; i++)
    {
        update(1, 0, m, i, i, -sum);
        update(1, 0, m, 0, i - 1, x);
 
        ll res = getVal(1, 0, m, 0, i);
        if (res < 0)
        {
            cout << n - i;
            return 0;
        }
    }
 
    cout << -1;
}

---

F - Tasty Cookie

Problem - F - Codeforces

추가 예정