Codeforces Round #583 후기 + 풀이

D번을 9틀했지만 E번을 풀어서 +38 받고 다시 퍼플 돌아갔다. :dhk: 

간만에 2.5시간 라운드인데, 확실히 30분 긴게 차이가 꽤 많이 나는것 같다.

---

A. Optimal Currency Exchange

간단하게 말하면, 1달러가 $d$ 루블이고 1유로가 $e$ 루블일 때, 달러와 유로를 최대한 많이 환전해서 루블을 최소화하는 문제.

다만 1달러짜리 지폐가 있는 것과는 달리 유로는 5유로 이상의 지폐만 고려한다.

달러를 0부터 $n/d$ 사이로 환전할 수 있으므로, 모든 경우를 고려해도 된다. $d$ 가 30정도고 $n$ 이 1e8이니까 이렇게 해도 몇백만 루프 안에 해결. 

#include <bits/stdc++.h>
using namespace std;
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
int main()
{
    int n, e, d;
    cin >> n >> d >> e;
    e *= 5;
    int ans = 987654321;
    for (int i = 0; i<=(n/d); i++)
    {
        int u = n - (i*d);
        int v = u/e;
        u -= v*e;
        ans = min(u, ans);
    }
    cout << ans << '\n';
}

---

B. Badges

남학생이 $b$명, 여학생이 $g$명 있는데 이 중 $n$명이 적당히 뽑혀 올 예정이다.

올 수 있는 남학생 / 여학생의 최솟값과 최댓값을 구해서, 양쪽 극단의 경우를 체크하면 되는 문제.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int b, g, n;
    cin >> b >> g >> n;
    b = min(b, n);
    g = min(g, n);
    int lb = n-b;
    int rb = n-g;
    cout << n+1 - lb - rb << '\n';
}

---

C. Bad Sequence

어떤 괄호 문자열이 주어졌을 때, 최대 한 번 두 문자의 위치를 바꿔서 올바른 괄호 문자열이 되게 할 수 있는지 묻는 문제.

 

괄호 문자열을 스택을 이용해서 판단하는 방법도 있지만, ( 를 +1로, ) 를 -1로 바꾸면 어떤 문자열이 올바른 괄호 문자열이 될 조건은 이 값들의 누적합을 이용해서 다음과 같이 나타낼 수 있다.

- 최종 결과 누적합이 0

- 누적합을 구해나가는 과정에서 한 번도 음수가 나오지 않는다.

 

첫 번째 조건은 (와 )의 개수가 같으면 만족된다. 이때, 조금만 생각해 보면 가장 이득이 되는 방법은 가장 앞에 나오는 )를 가장 뒤에 나오는 (와 교체하는 것임을 알 수 있어서, 이걸 그대로 판정해도 되고...

누적합을 구하면서 한 번이라도 -1보다 작은 값이 나온다면 교체를 통해 올바른 괄호 문자열을 만들 수 없음을 관찰해도 된다.

#include <bits/stdc++.h>
using namespace std;
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
string str;
int n;
int ct[202020];
int reff[2] = {-1,1};
int main()
{
    usecppio
    cin >> n >> str;
    ct[0] = reff[str[0]=='('];
    for (int i = 1; i<n; i++)
        ct[i] = ct[i-1] + reff[str[i]=='('];
    if (ct[n-1]!=0)
    {
        cout << "No";
        return 0;
    }    
    for (int i = 0; i<n; i++)
    {
        if (ct[i] < -1)
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

D번도 바로 짤 수 있을 것 같길래 코딩했는데, WA on Pretest 12를 계속 받다가 빡쳐서 E번으로 넘어가서 E번을 먼저 풀었다.

---

E. Petya and Construction Set

1부터 $2n$ 까지의 정점들이 있는 트리를 만드는데, 정점 $2i$ 와 $2i-1$ 사이에는 정확히 $d_i$ 개의 간선이 있어야 한다.

 

먼저, 홀수 노드들을 배치하자. 이때, $d_i$가 큰 홀수 노드를 최대한 왼쪽에 배치하는 식으로 정렬한다. 만약 $d_i$ 가 

2 2 3 1 3 과 같이 주어져 있다면, 각각의 홀수 노드 1 3 5 7 9를 9-5-3-1-7 로 배치한다는 뜻이다.

 

이때, 필요한 간선의 개수를 보면서 지금 있는 홀수 체인의 '위' 방향으로 새로운 노드를 배치한다. 즉 9의 경우, 10은 9로부터 3칸 떨어진 곳에 위치해 있으므로 3 위에 놓으면 된다. 5의 경우 1 위에 6을 놓으면 된다.

이러한 Construction이 항상 가능함을 보이는 것은 어렵지 않다. $d_i < n$ 이 보장되기 때문에...

또한, longest chain이 우리가 원하는 길이 ($d_i$ 보다 긴 것은 아무 문제가 없지만, 짧은 것은 문제가 될 수 있다. 따라서, 끝에 붙이는 게 가능한 경우 최대한 longest chain을 길게 유지하는 방향으로 해야 한다.

#include <bits/stdc++.h>
using namespace std;
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair<int, int>;
int d[101010];
int n;
 
deque <int> longest_chain;
vector <pii> v;
void printedge(int a, int b)
{
    cout << a << ' ' << b << '\n';
}
int main()
{
    usecppio
    cin >> n;
    int lcl = n;
    for (int i = 1; i<=n; i++)
    {
        cin >> d[i];
        v.push_back({d[i], i});
    }        
    sort(all(v),greater<pii>());
    for (int i = 0; i<n; i++)
        longest_chain.push_back(2*v[i].second-1);
    for (int i = 0; i<n-1; i++)
        printedge(longest_chain[i],longest_chain[i+1]);
    for (int i = 0; i<n; i++)
    {
        if (v[i].first == lcl-i)
        {
            longest_chain.push_back(2*v[i].second);
            lcl++;
            printedge(longest_chain[lcl-2],longest_chain[lcl-1]);
        }
        else
        {
            int dis = v[i].first;
            int targ = longest_chain[i+dis-1];
            printedge(targ,2*v[i].second);
        }
    }
}

push_back밖에 안 쓸건데 deque를 선언한 이유는, 코딩 들어가기 직전까지 홀수점들을 "큰 것을 바깥쪽" 으로 배치해야 된다고 생각해서 push_back과 push_front를 번갈아 쓰려고 했는데 생각해 보니 그냥 정렬순서대로 넣는게 맞았다. 

---

여기까진 풀었고, D를 계속 시도하다가 실패하고 라운드가 끝났다. :cry:

---

D. Treasure Island (라운드 중엔 못 풀었다 ㅠ)

점 $(1, 1)$ 에서부터 오른쪽 또는 아래로만 이동하면서 $(n, m)$ 에 도달하려고 하는데, 막힌 칸들은 통과할 수 없다.

최소 몇 개의 칸을 막아야 이동할 수 없게 만들 수 있을까?

 

관찰 1 : 일단 $(2, 1)$ 과 $(1, 2)$ 두 개를 막아 버리면 처음 출발점에서 아무것도 못 하게 되므로 답은 최대 2 이하이다.

 

처음 출발점에서 도착점에 갈 수 있는지 없는지는 dp를 돌든 bfs를 하든 (어차피 결과적으로는 같은 거지만) 알 수 있으므로, 답이 0인 경우는 바로 알 수 있다. 따라서 답이 1인 경우와 2인 경우만 찾으면 되는데...

 

나는 대충 이런 식으로 생각했다.

$\texttt{d[i]}$ = $(1, 1)$ 에서 거리가 $i$인 점들 중 처음에 도달 가능한 점의 개수 라고 정의하자. 이때, $d[1]$ 부터 $d[n+m-3]$ 까지 중 최소값이 답이지 않을까?

 

사실 지금 생각해보니 이상한거 같은데 (단순화하는 과정에서 정보를 꽤 많이 잃어버린다) 로직은 맞는데 코딩 실수인 줄 알고 파이썬으로도 다시 짜고...;;;

 

이걸로 끝나고 Whining 하고 있었는데 갓갓 BaaaaaaaaaaarkingDog 님이 1분만에 반례를 찾아 주셨다.

$\texttt{5 7}$
$\texttt{.......}$
$\texttt{...####}$
$\texttt{.#.....}$
$\texttt{#......}$
$\texttt{.......}$

이렇게 하면 거리가 몇인 점이든 다 2개 이상의 점이 방문 가능하지만, 중간에 1개 점을 막으면 경로가 사라진다.

 

사실 생각이 반정도밖에 안 된게, 원래 풀이는 "$(1, 1)$ 에서도 도달 가능하고, 뒤집어서 $(n, m)$ 에서 왼쪽 또는 위로만 움직이면서 닿을 수 있는 점" 의 개수를 세야 한다고 한다. :disappointed:

---

그래도 대충 이제 1900 실력 비슷하게는 온거 같은 느낌이 든다. 특히 E번 같은건 한달 전 정도만 해도 못 풀었을거 같은데... 

설마 오늘 라운드로 다시 블루 돌아가진 않겠지? ㅋㅋㅋㅋㅋ