[CF] Codeforces Round #805 (Div. 3)

https://codeforces.com/contest/1702

Dashboard - Codeforces Round #805 (Div. 3) - Codeforces

C번 안터졌으면 50점정도 올라서 그린 갔을텐데...

A. Round Down the Price (00:04)

정수 m이 입력되면, m보다 작거나 같은 최대 \( 10^k \)꼴의 수와의 차를 출력해야한다.

나는 m를 문자열로 입력받아서,  m-(1에 10를 m.length()-1번 곱한 수) 를 출력해 풀었다.

B. Polycarp Writes a String from Memory (00:18)

그냥 구현 문제이다.

서로 다른 3개의 문자만 있는 부분 문자열의 개수를 세면 된다.

나는 서로 다른 3개를 저장하는 vector를 관리해서 풀었다. 

vector의 erase, size 함수, 중복여부를 체크하는 변수를 이용해서 관리했는데, 이 방법이 바로 떠올라서 이렇게 구현했었는데, 더 나은 구현이 있다.

 

set을 이용하여, clear, empty, insert함수를 이용하면 중복 처리와 같은 부분들을 더 간단하게 구현할 수 있다.

중복 처리를 저절로 해주는 set의 특징을 이용해 set을 이용할 생각을 당시에도 했었지만, 저런 함수들을 많이 안써봤어서 그런지, 안전하게 vector를 이용했던 것 같다. 앞으로는 set 더 많이 써보면서 익숙해져야겠다.

C. Train and Queries (upsolved)

map을 이용한 문제라는 걸 알아채고, mp[u]에 u가 있는 인덱스 i를 전부 vector로 저장해두었다.

출력 시에 mp[a], mp[b]를 정렬하고,  mp[a][0] < mp[b][mp[b].size()-1] 이면 YES, 아니면 NO를 출력하도록 했다.

 

당시에는 위 풀이로 AC를 받았지만, 대회 끝나고 보니 내 풀이가 TLE로 터져있었다... 그래서 다시 생각해보니, u가 있는 인덱스 i를 전부 저장해 둘 필요 없이, 최대 i, 최소 i 오직 두 개만 저장해 두면 되었었다. 그러면 정렬을 할 필요가 없어서 TLE가 나지 않는다.

따라서 입력 받을 때에 최대 i, 최소 i를 보장해주고, 출력 시에 mp[a].first < mp[b].second 이면 YES, 아니면 NO를 출력하도록 하면 된다.

D. Not a Cheap String (00:50)

문자 a~z 가 1~26의 가격을 가지는데, 주어진 문자열의 가격은 구성하는 모든 문자들의 가격의 합이다.

주어진 p보다 주어진 문자열 w의 가격을 작게 하는 가장 긴 w의 부분 문자열을 출력해야 한다.

 

그냥 그리디하게 매번 알파벳 내림차순으로 하나씩 제거하면서 p보다 작은지 확인하면 된다.

E. Split Into Two Sets (upsolved)

계속 혼자 고민해 봤는데, 안풀려서 다른 사람들의 코드들을 보니, 이분 그래프라는 개념을 알게 되었다. 알고보니 백준 1707 이분 그래프 를 풀어 본 적이 있었다. 이분 그래프 개념을 사용한 문제를 2번째 만나보는 것 같은데, 이분 그래프인지 판단하려면, dfs를 이용해 각 정점에 서로 다른 값(1, 2)(색깔)을 준 뒤에, 인접한 정점에 같은 값이 있는 두 정점 쌍이 하나라도 있으면 이분 그래프가 아니고, 없으면 이분그래프 임을 판단하면 된다.

vector<int> g[20001];
int color[20001]; //0은 방문을 안함, 1은 그룹1, 2는 그룹2를 뜻한다.
void dfs(int x, int c)
{
  color[x]=c;
  for(int i=0;i<g[x].size();i++)
  {
    int y=g[x][i];
    if(color[y]==0) dfs(y, 3-c); //3-c는 c=1,2 -> c=2,1의 역할이다.
  }
}

백준 1707 이분 그래프 문제에서 내가 전에 이렇게 이분 그래프에 값을 주는 부분을 구현했었다.

구현할 때, 서로 다른 값(색깔)을 c=1, 2라 두면 그와 다른 색을 3-c을 이용해 간단히 할 수 있는 점을 기억해두면 좋을 것 같다.

이제 위 코드, 개념을 활용해서 이 문제를 풀어보자.

 

입력 부분에서 한 쌍의 두 수가 같은 경우, 어떤 수가 3번 이상 나온 경우는 무조건 이분 그래프가  될 수 없음을 ok변수에 반영하면 된다.

dfs를 이용해 그래프를 순회하면서 이미 방문한 곳(color[i]!=0) 의 값이 직전 정점과 색이 다른지 판단하여 ok변수에 반영하면 된다.

 

코드는 아래와 같다. 

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
bool ok;
ll n, a, b;
ll color[200005];
vector<ll> v[200005];
void dfs(ll x)
{
    for(auto nxt:v[x])
    {
        if(color[nxt])
        {
            if(color[nxt]!=3-color[x]) ok=false;
        }
        else
        {
            color[nxt]=3-color[x];
            dfs(nxt);
        }
    }
}
void solve()
{
    ok=true;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        if(a==b || v[a].size()>2 || v[b].size()>2) ok=false;
    }
    if(ok)
    {
        for(ll i=1;i<=n;i++)
        {
            if(color[i]) continue;
            color[i]=1;
            dfs(i);
        }
    }

    for(int i=1;i<=n;i++) v[i].clear(), color[i]=0;

    if(ok) cout<<"YES\n";
    else cout<<"NO\n";
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}