Codeforces Round #707 (Div. 1, Div. 2)

A - Alexey and Train

Problem - A - Codeforces

하라는 대로 구현하면 된다.

 

#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[101], b[101];
int tim[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
        for (int i = 1; i <= n; i++) cin >> tim[i];
 
        int ans = 0;
        for (int i = 1; i < n; i++)
        {
            ans += a[i] - b[i - 1] + tim[i];
            ans += (b[i] - a[i] + 1) / 2;
            ans = max(ans, b[i]);
        }
 
        ans += a[n] - b[n - 1] + tim[n];
        
        cout << ans << '\n';
    }
}

---

B - Napoleon Cake

Problem - B - Codeforces

접시위에 나폴레옹 케이크를 \(n\)개 쌓으려고 한다.

각각의 케이크를 쌓은 다음 시럽을 붓는데, 시럽을 부으면 위에서 \(a_i\)개의 케이크가 젖게 된다.

 

모든 케이크를 쌓고 시럽을 부은 다음, 각 케이크가 젖어있는지 아닌지 알아내야 한다.

 

케이크를 역순으로 살펴보면서, 현재까지 시럽을 부었을 때 몇 번 케이크까지 젖게 되는지 저장해 놓으면 \(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; }
 
int n;
int a[200001];
int ans[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 = 1; i <= n; i++)
        {
            cin >> a[i];
            ans[i] = 0;
        }
 
        int last = n + 1;
        for (int i = n; i >= 1; i--)
        {
            last = min(last, i - (a[i] - 1));
            if (last <= i) ans[i] = 1;
        }
 
        for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

A - Going Home

Problem - A - Codeforces

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

\(a_x + a_y = a_z + a_w\)를 만족하는 서로 다른 인덱스 \(x,y,z,w\)가 존재하는지 알아내고, 존재한다면 그 인덱스를 출력하면 된다.

 

\(a_i\)의 범위가 최대 250만이므로, 서로 다른 두 인덱스 \(i, j\)에 대해 \(a_i+a_j\)는 최대 500만이다.

어떤 배열에서 두 원소를 골랐을 때, 합이 \(x\)인 경우가 \(y\)가지라고 하자.

\(y > 3\)라면, 위의 조건을 만족하는 4개의 인덱스가 무조건 존재함을 알 수 있다.

* \(y \le 3\)이라면, 다음과 같은 경우에서 불가능하다.

ex) \(a = \{1, 1, 1, 3 \}\), 합이 4인 경우가 \(a_1 + a_4\), \(a_2 + a_4\), \(a_3 + a_4\)로 3가지지만, \(a_4\)가 전부 중복되므로 불가능

 

따라서 종합하면, 배열에서 서로 다른 2000만개의 쌍을 고를 수 있다면, 비둘기집의 원리에 의해 그 안에 적어도 문제의 답이 하나 존재한다는 사실을 알 수 있다.

\(n\)개 원소 중에 2개를 고르는 경우의 수는 \(\frac {n(n-1)}{2}\)이고, 이 값이 2000만이상이 되는 최소 \(n\)은 6326이다.

배열의 원소 수가 이보다 크더라도 그 중 6326개의 원소만 보면 그 안에 답이 무조건 존재하며, \(O(n^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 a[200001];
vector <pii> idx[5000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for (int j = 1; j < i; j++)
        {
            vector <pii>& cur = idx[a[i] + a[j]];
            cur.push_back({ i, j });
            if (cur.size() > 1)
            {
                for (int k = 0; k < cur.size(); k++) for (int l = k + 1; l < cur.size(); l++)
                {
                    pii xy = cur[k];
                    pii zw = cur[l];
 
                    if (xy.first == zw.first) continue;
                    if (xy.first == zw.second) continue;
                    if (xy.second == zw.first) continue;
                    if (xy.second == zw.second) continue;
 
                    cout << "YES\n";
                    cout << xy.first << ' ' << xy.second << ' '
                        << zw.first << ' ' << zw.second;
                    return 0;
                }
            }
        }
    }
 
    cout << "NO";
}

---

B - Two chandeliers

Problem - B - Codeforces

하루에 한 번씩 다른 색으로 빛나는 두 개의 샹들리에가 있다.

샹들리에 하나는 \(n\)일, 나머지 하나는 \(m\)일의 주기를 갖는데,

각 샹들리에에서 한 주기 동안 보이는 색은 모두 서로 다르다.

ex) 첫번째 샹들리에는 \(n\)일 동안 \(n\)개의 서로 다른 색으로 빛난다.

 

두 샹들리에를 동시에 켰을 때, \(k\)번째로 다른 색으로 빛나는게 며칠 후인지 알아내야 한다.

 

반대로 두 샹들리에가 같은 색으로 빛나는 날이 언제인지 알아보자.

어떤 색이 첫 번째 샹들리에에서는 \(a\)번째 차례, 두 번째 샹들리에에서는 \(b\)번째 차례에 빛난다고 하자.

그러면 다음과 같은 합동식을 세울 수 있다.

\(x \equiv a \pmod n\)

\(x \equiv b \pmod m\)

 

중국인의 나머지 정리로 \(x\)를 알아낼 수 있다.

 

두 샹들리에의 색은 \(lcm(n, 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, k;
ll a[500001];
ll b[500001];
 
ll aidx[1000001];
ll bidx[1000001];
 
pll ext_gcd(ll a, ll b)
{
    if (b == 0) return { 1, 0 };
    pll res = ext_gcd(b, a % b);
    ll x = res.second;
    ll y = res.first - a / b * x;
    return { x, y };
}
 
vector <ll> ls;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    memset(aidx, -1, sizeof aidx);
    memset(bidx, -1, sizeof bidx);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        aidx[a[i]] = i;
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        bidx[b[i]] = i;
    }
 
    ll g = gcd(n, m);
    ll l = n * m / g;
 
    ll ca = n / g;
    ll cb = m / g;
 
    pll res = ext_gcd(ca, cb);
 
    for (int i = 1; i <= 1000000; i++)
    {
        if (aidx[i] == -1 || bidx[i] == -1) continue;
 
        // nx + mz = bidx[i] - aidx[i];
        if ((bidx[i] - aidx[i]) % g) continue;
 
        ll wh = ((res.first * (bidx[i] - aidx[i]) * ca + aidx[i]) % l + l) % l;
        ls.push_back(wh);
    }
 
    sort(ls.begin(), ls.end());
 
    ll ans = l * (k / (l - ls.size()));
    ll rm = k % (l - ls.size());
 
    if (rm == 0)
    {
        ll cur = l - 1;
        while (binary_search(ls.begin(), ls.end(), cur--)) ans--;
 
        cout << ans;
    }
    else
    {
        ll lp = -1, rp = l - 1;
        while (lp + 1 < rp)
        {
            ll mp = (lp + rp) / 2;
            ll cnt = mp - (lower_bound(ls.begin(), ls.end(), mp) - ls.begin());
            if (cnt >= rm) rp = mp;
            else lp = mp;
        }
 
        ans += rp;
 
        cout << ans;
    }
}

---

C - Matrix Sorting

Problem - C - Codeforces

\(n \times m\) 크기의 두 표 \(A, B\)가 있다.

표는 각 열은 어떤 한 열의 값을 기준으로 stable sort할 수 있다.

 

\(A\)를 적당히 정렬해 \(B\)로 만들 수 있는지 여부를 알아내야 한다.

가능하다면, 그 순서를 출력한다.

 

현재 \(B\)의 어떤 \(x\)번째 열이 정렬되어 있다면, \(B\)는 마지막으로 \(x\)번째 열이 기준이 되어 정렬된 결과라고 생각할 수 있다.

\(x\)번째 열에서, 수 \(i\)가 연속되어 있는 행의 구간을 \([l_i, r_i]\)라고 하자.

어떤 \(y\)번째 열이 모든 구간 \([l_i, r_i]\) 내에서 정렬이 되어있다면 \(y\)번째 열이 마지막에서 두번째로 기준이 되어 정렬되었다고 생각할 수 있다.

 

이와 같은 식으로 정렬 기준이 되는 열을 계속해서 찾아나가면, 최종적으로 \(A\)를 어떤 순서로 정렬해야 \(B\)가 나오는지 순서가 나오게 된다.

실제로 그렇게 해서 정렬이 되는지 확인하면 된다.

 

이를 나이브하게 구현하면 \(O(nm^2)\)인데, 정렬되어 있는지 여부를 판단할 때 bitset을 이용해 상수커팅이 가능하고, 충분히 시간안에 돌아간다.

 

#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;
vector <vector<int> > a, b;
 
vector <int> ans;
bitset <1500> rv[1500];
bitset <1500> dif[1500];
 
int cache[1501];
void solve(bitset<1500> &bs)
{
    for (int i = 0; i < m; i++)
    {
        if (cache[i]) continue;
 
        bool flag = true;
        if (bs.count() != (bs | rv[i]).count()) continue;
 
        ans.push_back(i);
        bs |= dif[i];
 
        cache[i] = 1;
        solve(bs);
 
        break;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
 
    a.resize(n);
    for (int i = 0; i < n; i++)
    {
        a[i].resize(m);
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }
 
    b.resize(n);
    for (int i = 0; i < n; i++)
    {
        b[i].resize(m);
        for (int j = 0; j < m; j++)
        {
            cin >> b[i][j];
            if (i && b[i][j] < b[i - 1][j]) rv[j][i - 1] = 1;
            if (i && b[i][j] != b[i - 1][j]) dif[j][i - 1] = 1;
        }    
    }
 
    bitset <1500> bs;
    solve(bs);
 
    reverse(ans.begin(), ans.end());
    for (int x : ans)
    {
        stable_sort(a.begin(), a.end(), [&x](const vector <int>& a, const vector <int>& b) {
            return a[x] < b[x];
        });
    }
 
    bool flag = true;
    for (int i = 0; i < n; i++)
        if (a[i] != b[i]) flag = false;
 
    if (!flag)
    {
        cout << -1;
        return 0;
    }
 
    cout << ans.size() << '\n';
    for (int x : ans) cout << x + 1 << ' ';
}

---

D - Tiles for Bathroom

Problem - D - Codeforces

---

E - Subset Trick

Problem - E - Codeforces

추가 예정

---

F - Cupboards Jumps

Problem - F - Codeforces

추가 예정