Codeforces Round #718 (Div. 1 + Div. 2)

A - Sum of 2050

Problem - A - Codeforces

 

어떤 수가 \(2050 \cdot 10^k\)꼴로 나타내어지면 이를 2050-수라고 하자.

 

양의 정수 \(n\)을 가장 적은 개수의 2050-수의 합으로 나타내려면 몇 개가 필요한지 알아내야 한다.

 

\(n\)이 2050으로 나누어 떨어지지 않으면 일단 불가능하다.

가능하다면, 2050으로 나누었을 때 몫의 모든 자릿수의 숫자의 합을 다 더하면 된다.

 

#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 n; cin >> n;
        if (n % 2050)
        {
            cout << "-1\n";
            continue;
        }
 
        n /= 2050;
 
        ll ans = 0;
        while (n)
        {
            ans += n % 10;
            n /= 10;
        }
 
        cout << ans << '\n';
    }
}

---

B - Morning Jogging

Problem - B - Codeforces

\(n+1\)개의 정점이 있고, 인접한 두 정점을 각각 \(m\)개의 길이 잇고 있다.

 

\(m\)명의 사람이 0번부터 \(n\)번 정점까지 각각 하나의 길을 선택해 이동해야 한다.

서로 다른 두 사람이 같은 길을 선택할 수는 없다.

 

어떤 사람이 힘든 정도 \(l_i\)는 선택한 총 \(n\)개의 길 중 가장 짧은 길의 길이라고 할 때,

\(l_i\)의 합이 최소가 되기 위해 각 사람들이 골라야 하는 길을 알아내야 한다.

 

 

현재 존재하는 \(nm\)개의 길 중 가장 짧은 것을 하나 고르자.

남은 \(n-1\)개의 길은 그 구간에서 가장 긴 길이의 길을 고르는 것이 항상 이득이라는 사실을 알 수 있다.

 

이를 \(m\)번 반복하면 된다.

 

#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;
deque <ll> b[101];
multiset <pll> v;
int ans[101][101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        v.clear();
 
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            b[i].resize(m);
            for (int j = 0; j < m; j++)
            {
                ll x; cin >> x;
                b[i][j] = x;
                v.insert({ x, i });
            }
 
            sort(b[i].begin(), b[i].end());
        }
 
        for (int i = 0; i < m; i++)
        {
            auto it = *v.begin(); v.erase(v.begin());
            ll x = it.first;
            int idx = it.second;
            b[idx].pop_front();
 
            for (int j = 0; j < n; j++)
            {
                if (j == idx)
                {
                    ans[j][i] = x;
                    continue;
                }
 
                ll res = b[j].back();
                b[j].pop_back();
                ans[j][i] = res;
                v.erase(v.find({ res, j }));
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++) cout << ans[i][j] << ' ';
            cout << '\n';
        }
    }
}

---

C - Fillomino 2

Problem - C - Codeforces

\(n \times n\)크기의 판이 있다.

이 판의 주 대각선에 1 부터 \(n\)까지의 정수의 순열이 쓰여 있다.

이 판의 주 대각선을 포함한 아랫부분만을 사용해, 다음과 같이 판을 분할해야 한다.

 

1. 총 \(n\)개의 구간으로 판을 분할 해야 한다.

2. 각 구간은 하나의 주 대각선 칸을 포함해야 한다.

3. 그 주 대각선에 쓰인 수가 \(x\)라면, 그 구간의 넓이도 \(x\)여야 한다.

 

주 대각선의 맨 위에 있는 수 부터 시작해서, 한 칸씩 넓혀보자.

우선순위를 다음과 같이 두고 넓혀가면 된다.

 

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 ans[501][501];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int r; cin >> r;
        ans[i][i] = r;
 
        int x = i, y = i;
        for (int j = 0; j < r - 1; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                int nx = x + "1210"[k] - '1';
                int ny = y + "0121"[k] - '1';
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (ans[nx][ny]) continue;
 
                x = nx, y = ny;
                break;
            }
 
            ans[x][y] = r;
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++) cout << ans[i][j] << ' ';
        cout << '\n';
    }
}

---

D - Explorer Space

Problem - D - Codeforces

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

각각의 칸에서, 인접한 다른 칸까지 이동하는데 필요한 비용이 주어진다.

 

모든 칸에 대해, 총 \(k\)번 이동해 원래의 칸으로 돌아오는데 필요한 최소 비용을 각각 구해야 한다.

 

 

먼저, \(k\)가 홀수면 불가능하다.

 

우리가 어떤 칸에서 시작해서, 단순히 \(\frac k2\)번 이동한다고 할 때 필요한 비용의 최소값을 \(x\)라고 하자.

나머지 \(\frac k2\)번은 다시 계산할 필요가 없다.

지금 구한 그 길을 역순으로 이동해 돌아오면 되기 때문에, \(2x\)가 답이다.

 

따라서 \(O(nmk)\) 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, m, k;
 
ll r[501][501];
ll d[501][501];
 
ll dp[11][501][501];
ll solve(int k, int x, int y)
{
    ll& ret = dp[k][x][y];
    if (ret != -1) return ret;
    if (k == 0) return ret = 0;
 
    ret = 1e18;
    if (y + 1 < m)
    {
        ll res = solve(k - 1, x, y + 1) + r[x][y];
        ret = min(ret, res);
    }
    if (y - 1 >= 0)
    {
        ll res = solve(k - 1, x, y - 1) + r[x][y - 1];
        ret = min(ret, res);
    }
    if (x + 1 < n)
    {
        ll res = solve(k - 1, x + 1, y) + d[x][y];
        ret = min(ret, res);
    }
    if (x - 1 >= 0)
    {
        ll res = solve(k - 1, x - 1, y) + d[x - 1][y];
        ret = min(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(dp, -1, sizeof dp);
 
    cin >> n >> m >> k;
    if (k % 2)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++) cout << "-1 ";
            cout << '\n';
        }
        return 0;
    }
 
    k /= 2;
 
    for (int i = 0; i < n; i++) for (int j = 0; j < m - 1; j++)
        cin >> r[i][j];
 
    for (int i = 0; i < n - 1; i++) for (int j = 0; j < m; j++)
        cin >> d[i][j];
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ll res = solve(k, i, j);
            cout << res * 2 << ' ';
        }
 
        cout << '\n';
    }
}

---

E - Group Photo

Problem - E - Codeforces

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

이 수열의 각 원소를 문제에 나와 있는 두 집합 \(C, P\)중 하나로 배정했을 때,

\(C\)에 해당하는 원소의 합보다 \(P\)에 해당하는 원소의 합이 더 큰 경우의 수를 구해야 한다.

 

관찰을 열심히 해보면, 조건에 맞는 C와 P의 조합은 다음의 5가지로 나눌 수 있게 된다.

 

(정규표현식)

1. C*(PC)*P*

2. (PCC)C*(PC)*P*

3. C*(PC)*P*(PPC)

4. (PCC)C*(PC)*P*(PPC)

 

/*

위 4개는 다음과 같다.

(PCC)?C*(PC)*P*(PPC)?

*/

 

5. P*C*

 

각각의 경우에 가능한 경우의 수를 투포인터 등으로 \(O(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; }
 
const int N = 200001;
const ll MOD = 998244353;
 
ll n;
ll sum;
ll a[N];
 
ll solve(ll L, ll R, ll preSum)
{
    if (L > R) return 0;
    if (preSum * 2 >= sum) return 0;
 
    ll res = 0;
 
    ll lsum = preSum;
    ll r = L;
    while (r + 2 <= R && (lsum + a[r + 2]) * 2 < sum)
    {
        r += 2;
        lsum += a[r];
    }
 
    ll l = L;
    res += (r - l) / 2 + 1;
    res %= MOD;
 
    for (l += 2; l <= R; l += 2)
    {
        lsum += a[l - 1];
        while (lsum * 2 >= sum && l <= r)
        {
            lsum -= a[r];
            r -= 2;
        }
 
        if (l > r) break;
        res += (r - l) / 2 + 1;
        res %= MOD;
    }
 
    if (L + 1 <= R && (preSum + a[L + 1]) * 2 < sum)
    {
        preSum += a[L + 1];
        L++;
 
        ll lsum = preSum;
        ll r = L;
        while (r + 2 <= R && (lsum + a[r + 2]) * 2 < sum)
        {
            r += 2;
            lsum += a[r];
        }
 
        ll l = L;
        res += (r - l) / 2 + 1;
        res %= MOD;
 
        for (l += 2; l <= R; l += 2)
        {
            lsum += a[l - 1];
            while (lsum * 2 >= sum && l <= r)
            {
                lsum -= a[r];
                r -= 2;
            }
 
            if (l > r) break;
            res += (r - l) / 2 + 1;
            res %= MOD;
        }
    }
 
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        sum = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            sum += a[i];
        }
 
        ll ans = 0;
 
        ans += solve(0, n, 0);
        ans %= MOD;
 
        ans += solve(3, n, a[2] + a[3]);
        ans %= MOD;
 
        ans += solve(0, n - 3, a[n]);
        ans %= MOD;
 
        ans += solve(3, n - 3, a[2] + a[3] + a[n]);
        ans %= MOD;
 
        if (n >= 4)
        {
            ll tsum = a[n] + a[n - 1];
            for (int i = n - 2; i >= 2; i--)
            {
                if (tsum * 2 < sum)
                    ans = (ans + 1) % MOD;
 
                tsum += a[i];
            }
        }
 
        //cout << "ANS : ";
        cout << ans << '\n';
    }
}

---

F - Reunion

Problem - F - Codeforces

추가 예정

---

G - Starry Night Camping

Problem - G - Codeforces

추가 예정

---

H - Fly Around the World

Problem - H - Codeforces

추가 예정