[codeforces] Codeforces Round #744 (Div. 3)

A. Casimir's String Solitaire

- 수학 문제 

 

- 주어진 문자열에서 아래의 두 연산중 하나를 수행한다.

• 임의의 A 와 B를 제거 
• 임의의 B 와 C를 제거

- 이때 문자열을 ""로 만들 수 있으면 YES , 아니면 NO를 출력하는 문제이다.

 

- 해결방법은 간단하다.

 

- 문자열에서 ABC 각각의 개수를 세고 A + C = B 가 성립하면 ""로 만들 수 있다.

반성 - 주어진 입력의 크기를 보지 못하고 완전탐색으로 모든 경우의 수를 구하여 풀려고 했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        string s;

        cin >> s;
        int alpha[3] = {0, 0, 0};

        for (int i = 0; i < s.length(); i++)
        {
            alpha[s[i] - 'A']++;
        }
        if (alpha[0] + alpha[2] == alpha[1])
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
}

 

B. Shifting Sort

- 구현 문제

 

- 주어진 연산으로 배열을 정렬하는 문제 

- 연산은 다음과 같다.

• 배열안에서 구간 [l, r] 을 정한뒤 왼쪽으로 쉬프팅하는 횟수 d를 정한다.
• 그 구간만 d번 쉬프팅한 뒤 그 구간만 배열을 업데이트한다. 

- 이 문제의 핵심은 구간과 쉬프팅하는 횟수를 자신이 정해야한다는것이다.

- 선택정렬이나 삽입정렬 처럼 "이미 정렬된 구간" 을 만드는 방향으로 연산을 정하면 문제를 해결할 수 있다.

- 정렬되어 있지 않은 구간에서 최소값을 찾고 그 값을 그 구간의 맨 왼쪽으로 옮기면된다.

- rotate 함수를 %연산을 사용하여 구현할 수 있다. (또는 std::rotate)

반성 - 주어진 문제를 제대로 해석하지 못하여 '최소' 횟수를 구하는 문제인줄 알았다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

void rotate(vector<int> &el, int lo, int hi, int k)
{
    vector<int> tmp(el.begin() + lo, el.begin() + hi);
    auto it = tmp.end();
    tmp.insert(it, el.begin() + lo, el.begin() + hi);
    k %= (tmp.size() / 2);
    for (int i = lo, h = k; i < hi; i++, h++)
    {
        el[i] = tmp[h];
    }
}

int N;
vector<vector<int>> solve(vector<int> &el)
{
    vector<vector<int>> ret;
    for (int i = 0; i < N; i++)
    {
        int min = min_element(el.begin() + i, el.end()) - el.begin();
        if (min != i)
        {
            rotate(el, i, N, min - i);
            ret.push_back({i + 1, N, min - i});
        }
        else
        {
            continue;
        }
    }
    return ret;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> N;
        vector<int> el;
        el.resize(N);
        for (int i = 0; i < N; i++)
        {
            cin >> el[i];
        }

        vector<vector<int>> els = move(solve(el));
        cout << els.size() << "\n";
        for (int i = 0; i < els.size(); i++)
        {
            for (int j = 0; j < els[i].size(); j++)
            {
                cout << els[i][j] << " ";
            }
            cout << "\n";
        }
    }
}

 

C. Ticks

- 구현 문제

 

- 주어진 2차원 배열을 주어진 패턴으로 만들 수 있는지 체크하는 문제이다.

 

- 이 문제는 오른쪽 아래에서부터 왼쪽 위에서부터 패턴을 그리면 문제를 해결할 수 있다.

- 탐색하면서 만약 '.' 를 만나게되면 바로 false 를 반환하게하고

- '*' 만 있으면 좌표들을 map에 넣어 마지막에 모든 '*'들의 개수와 같은지 확인하면된다. 

반성 - 2d vector 에선 꼭 resize하기전에 clear를 해주자

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;
vector<vector<char>> board;
int n, m, k;

vector<pair<int, int>> painted;
map<pair<int, int>, int> chck;

bool erase1(int i, int j, int d)
{
    for (int h = 0; h <= d; h++)
    {
        if (i - h < 0 || j + h >= m || j - h < 0)
        {
            return false;
        }
        if (board[i - h][j + h] == '.' || board[i - h][j - h] == '.')
        {
            return false;
        }
    }
    chck[{i, j}]++;
    for (int h = 1; h <= d; h++)
    {
        chck[{i - h, j + h}]++;
        chck[{i - h, j - h}]++;
    }
    return true;
}

string solve()
{
    for (int i = painted.size() - 1; i >= 0; i--)
    {
        for (int h = k; h < n; h++)
        {
            // 밑에서부터 체크하므로
            if (erase1(painted[i].first, painted[i].second, h) == false)
                break;
        }
    }
    if (chck.size() == painted.size())
    {
        return "YES";
    }
    return "NO";
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;
        board.clear();
        board.resize(n, vector<char>(m));
        painted.resize(0);
        chck.clear();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> board[i][j];
                if (board[i][j] == '*')
                {
                    painted.push_back({i, j});
                }
            }
        }
        cout << solve() << "\n";
    }
}

 

D. Productive Meeting

- 그리디 문제

 

- 각 사람마다 미팅을 할 수 있는 횟수가 정해져있다.

- 미팅은 두명씩 이루어진다.

- 이때 최대 몇번할 수 있는지와 누가 누구랑 미팅하는지 출력하는 문제이다.

 

- 사람들 중에서 가장 많이 미팅 횟수가 남은 두사람 TOP1, TOP2를 선택하면된다.

 

- 만약 어느 순간에서 TOP1와 임의의 사람 A를 선택해서

- 결과로 최대미팅횟수가 나왔다고 가정해보자.

 

- 그 순간에서 A와 TOP2 를 교체하면

- TOP2와 짝이었던 B는 A와 짝이 맺어지게되고

- TOP2 와 TOP1 짝이 맺어지게되며, 결과는 변하지 않는다.

- 즉, 손해가 없으므로 그때 그때 가장 많이 미팅 횟수가 남은 두사람을 선택하게되면

- 문제는 해결된다.

 

- 이때 최대값을 리턴해주는 max heap 자료구조를 사용하면 구현하기가 편하다.

  (우선순위 큐)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            pq.push({a, i + 1});
        }

        vector<pair<int, int>> answer;
        pair<int, int> top1, top2;
        while (true)
        {
            top1 = pq.top();
            if (top1.first == 0)
            {
                break;
            }
            pq.pop();

            top2 = pq.top();
            if (top2.first == 0)
            {
                break;
            }
            pq.pop();

            pq.push({top1.first - 1, top1.second});
            pq.push({top2.first - 1, top2.second});

            answer.push_back({top1.second, top2.second});
        }

        cout << answer.size() << "\n";
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i].first << " " << answer[i].second << "\n";
        }
    }
}

 

E1. Permutation Minimization by Deque

- deque 문제

 

- 주어진 입력에대해 순서대로 deque에 집어넣어 사전순으로 제일 앞에 오도록 출력하는 문제

 

- 입력하는 부분에서 front 와 값비교만 하면 문제는 해결된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        deque<int> answer;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            if (!answer.empty() && answer.front() > a)
            {
                answer.push_front(a);
            }
            else
            {
                answer.push_back(a);
            }
        }
        for (int i = 0; i < n; i++)
        {
            cout << answer[i] << " ";
        }
        cout << "\n";
    }
}

 

E2. Array Optimization by Deque

- 그리디 문제

 

- 역방향의 개수가 최소가 되도록 deque를 구성하는 문제.

  (inversion i < j and di > dj)

 

- 주어진 입력 a를 deque 에 넣는다.

- 이 때 front 와 back 둘중 하나를 선택을 할 수 있으며

- 역방향의 개수는 deque 안에있는 값들에 의해 정해진다.

- 즉, deque 가 어떻게 구성되는지 몰라도 된다는것이다.

 

- 그러므로 그때 그때 집어넣을때마다 

- 그 값보다 작은값들의 개수 와 큰것들의 개수 중 작은쪽을 선택하면 문제를 풀 수 있다.

 

- 하지만 O(N)으로 모든 값을 비교하면 시간초과가 뜬다.

 

- 그러므로 시간 복잡도를 O(lgn)으로 줄여야하며

- 이를 수행할 수 있게 해주는 자료구조로 세그먼트 트리가 있다.

- 주어진 입력을 모두 다시 값을 매겨주어

  (정렬 순으로 0~ : 구간을 설정하기가 편해진다 ex. LCA )

- 순서대로 세그먼트 트리에 넣어 구간을 구간에 포함된 원소의 수를 업데이트하면

- 시간 초과 없이 문제는 해결된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>

#include <queue>

using namespace std;


struct RQ
{
    using ll = int;
    const ll OUT_OF_BOUNDS_ = 0;

    int n;
    vector<ll> range;
    RQ(const vector<ll> &array)
    {
        n = array.size();
        range.resize(n * 4 + 4);
        init(array, 0, n - 1, 1);
    }
    ll op(ll a, ll b)
    {
        return a + b;
    }
    ll init(const vector<ll> &array, int left, int right, int node)
    {
        if (left == right)
            return range[node] = array[left];
        int mid = (left + right) / 2;
        ll leftValue = init(array, left, mid, node * 2);
        ll rightValue = init(array, mid + 1, right, node * 2 + 1);
        return range[node] = op(leftValue, rightValue);
    }
    ll query(int left, int right, int node, int nodeLeft, int nodeRight)
    {
        if (right < nodeLeft || nodeRight < left)
            return OUT_OF_BOUNDS_;
        if (left <= nodeLeft && nodeRight <= right)
            return range[node];
        int mid = (nodeLeft + nodeRight) / 2;
        return op(query(left, right, node * 2, nodeLeft, mid),
                  query(left, right, node * 2 + 1, mid + 1, nodeRight));
    }
    ll query(int left, int right)
    {
        return query(left, right, 1, 0, n - 1);
    }
    ll update(int index, ll newValue, int node, int nodeLeft, int nodeRight)
    {
        if (index < nodeLeft || nodeRight < index)
            return range[node];
        if (nodeLeft == nodeRight)
            return range[node] = newValue;
        int mid = (nodeLeft + nodeRight) / 2;
        return range[node] = op(
                   update(index, newValue, node * 2, nodeLeft, mid),
                   update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
    }
    ll update(int index, int newValue)
    {
        return update(index, newValue, 1, 0, n - 1);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        long long answer = 0;
        vector<int> v(n);
        map<int, int> mp;

        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
            mp[v[i]] = 1;
        }

        int value = 0;
        for (auto &it : mp)
        {
            it.second = value++;
        }
        RQ rq(vector<int>(n, 0));

        for (int i = 0; i < n; i++)
        {
            int mid = mp[v[i]];
            int left = rq.query(0, mid - 1);
            int right = rq.query(mid + 1, n - 1);
            answer += min(left, right);

            rq.update(mid, rq.query(mid, mid) + 1);
        }

        cout << answer << "\n";
    }
}

F. Array Stabilization (AND version)

?

G. Minimal Coverage

- dp 문제

 

- 구간의 길이가 담겨진 배열 A가 입력으로 주어진다. (1<= A[i]<= 1000) 

- 이때 첫번째 구간 (0, A[0]) 에서부터 순서대로 구간을 만들어 나간다.

- 이후 구간을 만드는 규칙은 다음과 같다.

• 구간은 start 와 end로 이루어진다. (첫번째구간에서 0은 start)
• start는 이전 구간의 end이다.
• 이전의 end 가 x, 구간의 길이가 d 이면 다음구간은 [x,x+d], [x−d,x] 중 하나가된다. (x+d 와 x-d 는 end)

- 이런 규칙에 의해 i = 0 ~ n-1 까지 순서대로 구간들을 만들고

- 만들어진 구간 전부를 커버할 수 있는 구간을 구할 수 있다.

- 이 구간의 길이를 최소화한 값을 출력해야 하는 문제이다.

 

- 풀이 (recursive)

(https://codeforces.com/contest/1579/submission/130442295 코드를 보고 작성한 풀이)

 

- 최소값을 구하는 문제이기 때문에, 모든 경우의 수를 구하고 그중 최소값을 선택하면 답을 낼 수 있다.

- 하지만 주어진 A의 크기는 10^4 이므로, 완전탐색하면 답을 내는데 오래걸릴것이다.

- 그러므로 중복된 계산을 피하는 dp 를 사용하는 방식으로 접근해봐야한다.

 

- 문제에서 주어진 정보중 하나인 '순서'

- 앞에서부터 차근차근 구간을 만들어간다는것.

- 즉, 배열의 '인덱스' 에서 만들어온 구간들이 다르지만

- 만약 구간을 구성해온 최소값과 최대값, 그리고 이 지점에서의 end 값이 같으면

- 그 이후에 오는 최적의값을 한번만 구하면 다시 계산하지 않아도 됨을 의미한다.

 

- 한 상태에 대해 두 부분문제로 나뉘므로

- 이를 식으로 나타내면 다음과 같을것이다.

 

dp = idx 에서 [lo, hi] 가 전체 구간을 포함하고 end 가 x일때 만 들 수 있는 전체 구간을 포함하는 최소의 길이.

 

dp[idx][lo][hi][x] = min(dp[idx + 1][min(lo, x)][max(hi, x+a[idx])][x + a[idx]

                                   , dp[idx+1][min(lo, x- a[idx])][max(hi, x)][x - a[idx]] );

 

- 하지만 이 식은 정보가 너무 많으며 모두 저장하기위해선 많은 메모리가 필요하다.

 

- 그러므로 정보들을 압축해야하며 이는 상대적인 거리로 표현하여 줄일 수 있다.

- 즉,

base 에서 left 만큼 떨어진 거리로 x를 표현하는것이다.

 

 

- 다음 idx의 left는 left -a[idx] 또는 left+a[idx] 가 된다.

- 여기서 주의할점은 left - a[idx]이다.

• 왼쪽으로 구간이 확장 : left -a[idx] < 0 일때 , base 가 변경됨을 의미한다.

- 이부분을 예외 처리하면

- 우리가 구하고자하는 lo~hi 값은 우리가 들렀던 left 중에서의 최댓값이라 생각할 수 있으며 

- 이는 다음과 같은 식을 세울 수 있다.

 

dp[idx][left] = base에서 left만큼 떨어진 거리에서 idx 이후부터 만들 수있는 left + right의 최소 길이.

dp[idx][left] = min(dp[idx+1][left + a[idx]] ,

                                                                (left >= a[idx]) ? max(left, dp[idx + 1][left - a[idx]] :                                              INF))

- 문제는 왼쪽 구간으로의 확장을 예외처리 했다는것이다.

 

- 왼쪽 구간으로의 확장은 base를 업데이트 시켜줘야한다는것을 의미한다.

- 이런 업데이트 과정에서 우리는 이전까지 만들어왔던 최대 길이를 알아야한다. (hi를 left로 삼아야 하므로)

- 하지만 이는 앞에서 봤던 식에서 볼 수 있듯이 정보가 많이 필요하므로 다른 방식으로 접근해야한다.

 

- 우리가 구하고자 하는 최소화시키고자하는 값은 base 에서부터 left까지가는 max left 값이다.

- base를 증가시키는것은 그 값만큼 왼쪽으로 확장시키는 허용 값을 늘리는것과 같다.

- 따라서 base를 0부터 시작하여  max값까지 dp[0][base] 값을구해 이 값들중 최소값을 구하면

- 문제는 해결된다.

 

- max값은 최악의 경우를 생각해서 정할 수 있다.

- 생각할 수 있는 구간의 최소 길이의 최악의 값은 2000인데

- 길이가 2000 이면 이후 부턴 - + 를 잘 조절해서 그 구간 내부에 구간을 설정할 수 있기 때문이다.

- 그러므로 left 의 최대 값은 2000이되고 base의 max 는 그것의 절반인 1000이 된다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> A;
int dp[10002][2001];

int solve(int idx, int left)
{
    if (left >= 2001)
        return left;

    int &ret = dp[idx][left];
    if (ret > 0)
        return ret;
    if (idx == A.size())
        return ret = left;

    ret = solve(idx + 1, left + A[idx]);
    if (left >= A[idx])
        ret = min(ret, max(left, solve(idx + 1, left - A[idx])));

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        A.resize(n);
        for (int i = 0; i < n; i++)
        {
            cin >> A[i];
        }

        int ret = INT_MAX;
        for (int i = 0; i <= A.size(); i++)
            memset(dp[i], -1, sizeof(dp[i]));

        for (int b = 0; b <= 1000; b++)
        {
            ret = min(ret, solve(0, b));
        }

        cout << ret << "\n";
    }
    return 0;
}

 

 

 

 

- 풀이 (iterative)

( https://www.youtube.com/watch?v=JRuAgCCwi0M 의 코드를 보고 작성한 풀이)

 

- 답의 범위는 1~2000 이다. 

- 그러므로 답이 나올 수 있는 공간은 2000 * A.size() 임을 알 수 있으며

- 이를 i = 0 부터 하나씩 업데이트 하여 위에서와 같이 idx 와 left로 dp를 구성하여

- 답이 될 수 있는모든 경우의 수를 구할 수 있는 충분한 크기이다. 

- left + a[i] 와 left - a[i] 의  4가지 가능한 경우(확장과 유지)를 처리해주면 문제를 해결할 수 있다.

- 이때 부분문제를 해결하는데 idx +1 와 idx 만 사용하므로 슬라이딩 윈도를 활용하여 메모리 공간을 줄일 수 있다.

 

- 이렇게 문제를 해결할 경우 이전 까지 만든 길이를 전부 알고 있으므로 왼쪽으로의 확장은

- wnd[cur][left] + a[i] - left 가 확장된 길이가 되고 left = 0 일때와 비교하여 업데이트 시켜주면 된다.

 

int solve()
{
    int wnd[2][2001];
    int nxt = 1;
    int cur = 0;
    fill(&wnd[cur][0], &wnd[cur][0] + 2001, INF);
    wnd[cur][0] = 0;
    for (int i = 0; i < a.size(); i++)
    {
        fill(&wnd[nxt][0], &wnd[nxt][0] + 2001, INF);
        for (int left = 0; left < 2001; left++)
        {
            if (wnd[cur][left] == INF)
            {
                continue;
            }

            // plus
            if (left + a[i] < 2001)
            {
                int update = 0;
                // 범위 안
                if (left + a[i] < wnd[cur][left])
                {
                    update = wnd[cur][left];
                }
                // 범위 밖 -> 확장 가능성
                else
                {
                    update = left + a[i];
                }
                wnd[nxt][left + a[i]] = min(wnd[nxt][left + a[i]], update);
            }

            // minus
            // 범위 안
            if (left - a[i] >= 0)
            {
                wnd[nxt][left - a[i]] = min(wnd[nxt][left - a[i]], wnd[cur][left]);
            }
            // 범위 밖 -> 확장가능성 -> 맨 왼쪽에 오게되니 0 (base 업데이트)
            else
            {
                wnd[nxt][0] = min(wnd[nxt][0], wnd[cur][left] + a[i] - left);
            }
        }
        nxt = (nxt + 1) % 2;
        cur = (cur + 1) % 2;
    }
    return *min_element(&wnd[cur][0], &wnd[cur][0] + 2001);
}

 

- 풀이 (bisearch)

-  lo = 1, hi = 2000 으로 설정하고

- mid 값을 구하여 mid값이 길이가 될 수 있는지 체크하는 풀이방법.