[C++] Codeforces Round #747 (Div. 2)

1. 문제 출처

https://codeforces.com/contest/1594

Dashboard - Codeforces Round #747 (Div. 2) - Codeforces

 

 

 

 

 

2. 문제 A. Consecutive Sum Riddle / solved

정수 $n \; (1 \leq n \leq 10^{18})$이 주어졌을 때, $l$부터 $r$까지의 합이 $n$이 되는 $l$과 $r$을 출력하는 문제.

$-k + k + (k + 1) = k + 1$ 인 점을 이용해서 문제를 해결할 수 있다.

 

 

 

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testcase; cin >> testcase;
    while (testcase--) {
        long long n; cin >> n;
        cout << -(n - 1) << " " << n << "\n";
    }

    return 0;
}

 

 

 

 

 

 

 

3. 문제B. Special Numbers / solved

 

어떤 양의 정수 $x$를 $n$의 $t$제곱들의 합으로 나타낼 수 있다면, $x$를 "특별"하다고 표현한다. 단, $t$는 서로 중복되어서는 안 된다. 예를 들어, $17$은 $4^2 + 4^0$으로 표현할 수 있기 때문에 특별한 정수이다. $(n = 4, t = 0, 2)$

 

 

 

 

문제에서 $n$과 $k$가 주어졌을 때, $n$의 $t$제곱들의 합으로 나타낸 여러 수들 중 $k$번째로 큰 수를 구하는 것이 목표이다. 정답이 매우 커질 수 있기 때문에, $10^9 + 7$로 나눈 나머지 값을 정답으로 출력한다.

 

 

 

 

 

처음, 직접 손으로 작은 수부터 특별한 수들을 나열해 보다가 표와 같은 규칙을 알아낼 수 있었다. 다음 표는 n=3인 경우, 특별한 수를 오름차순으로 나열한 것이다.

 

 

 

n= 3인 경우의 예시

 

 

 

위의 표에서 알아낼 수 있는 점은 $k$의 $i$번째 비트가 켜져 있는 경우, $n^{i-1}$을 정답에 더해주는 것이다.

주의해야할 점은 연산마다 MOD값으로 나머지 연산을 계속 진행해줘야 하는 것이고, 정수형의 overflow방지를 위해 자료형을 long long으로 사용을 하였다.

 

 

 

 

 

#include <iostream>
#define MOD 1000000007
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testcase; cin >> testcase;
    while (testcase--) {
        int n, k; cin >> n >> k;

        long long answer = 0;
        long long multiplier = 1;
        for (int bitIndex = 0; bitIndex < 32; ++bitIndex) {
            if (k & (1 << bitIndex)) {
                answer += multiplier;
                answer %= MOD;
            }
            multiplier *= n;
            multiplier %= MOD;
        }
        cout << answer << "\n";
    }

    return 0;
}

 

 

 

 

 

 

 

4. 문제C. Make Them Equal / solved

 

문자열 S가 주어졌을 때, 문자열 S를 문자 C로만 이루어져 있게 주어진 연산을 활용하여 만들어야 하는 문제.

한 번의 연산에서 하는 행동: $(1 \leq x \leq n)$인 $x$를 고른다. S에 포함된 각 문자를 순회하며 해당 문자 $\text{index}$가 $x$로 나누어 떨어지지 않는다면 해당 문자를 C로 바꿀 수 있다.

 

 

 

if (s[i] % x) s[i] = c;

 

 

 

문제를 읽고 바로 알아낼 수 있었던 것은 최대 연산 횟수는 2회가 넘어가지 않는다는 점이다. 그 이유는 S의 마지막 index를 $x$로 선택하게 되면, 마지막 전까지의 모든 문자를 c로 변경할 수 있고, 마지막 전 index를 선택하면 S의 마지막 문자도 c로 변경을 할 수 있게 된다. 그 외의 경우를 파악하기 위해 0번, 1번의 연산 수행으로 모든 문자를 바꿀 수 있는 상황을 생각해 보았다.

 

 

 

• 0번의 연산으로 문자열S의 모든 문자를 c로 변경할 수 있는 경우: 문자열 S가 모두 c로 이루어짐.
• 1번의 연산으로 문자열S의 모든 문자를 c로 변경할 수 있는 경우
  • 문자열 S의 마지막 문자가 c인 경우: x를 마지막 index로 설정 <생략 가능, 밑의 조건에서 포함됨>
  • 문자열의 중간~마지막 문자 중 c가 있는 경우: 해당 index를 x로 설정
    문자열의 중간부터 탐색을 진행하는 이유는, 그 전 index를 x로 설정하게 되면 문자열이 끝나기 전에 다시 확인하지 못하는 지점이 생기기 때문이다.
    
    
    
    

    

    문자열의 중간index부터 탐색을 진행하는 이유 (초록색: x로 설정, 노란색: 탐색가능)

    
    
    
• 2번의 연산으로 문자열 S의 모든 문자를 c로 변경할 수 있는 경우: 위 2가지를 제외한 나머지 경우
  
  
  

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testcase; cin >> testcase;
    while (testcase--) {
       int stringLen; cin >> stringLen;
       char c; cin >> c;
       string s; cin >> s;

       bool isStrange = false;
       for (auto ch : s)
        if (ch != c) {
            isStrange = true;
            break;
        }

        // 모든 문자열이 c로 이루어져 있음
        if (!isStrange) {
            cout << 0 << "\n";
            continue;
        }

        bool notFound = true;
        // 1번의 연산 수행으로 끝내는 경우 : 중간 ~ 마지막 문자가 c
        for (int x = stringLen / 2; x < stringLen && notFound; ++x) {
            if (s[x] == c) {
                cout << 1 << "\n";
                cout << x + 1 << "\n";
                notFound = false;
            }
        }

        if (notFound) {
            cout << 2 << "\n";
            cout << stringLen - 1 << " " << stringLen << "\n";
        }
    }

    return 0;
}

 

 

 

 

 

 

 

5. 문제 D. The Number of Imposters

 

게임에서 $n$명의 플레이어들이 <Among There>라는 게임을 진행하며, 각 플레이어들은 $1$부터 $N$까지 번호가 매겨져 있다. 플레이어들은 채팅창을 통해서 $M$개의 의견을 남길 수 있고, 의견은 $i j c$ 의 형식을 갖는다. 이는 플레이어 $i$가 말하길, 플레이어 $j$는 $c$의 역할을 가지고 있다 라는 의미이다. 게임에서 역할은 2가지 종류인데 "임포스터"와 "승무원"이다.

임포스터들은 항상 거짓말을 하고, 승무원들은 항상 올바른 정보만을 말한다. 이때 가능한 많은 임포스터의 수를 찾을 수 있게 하는 것이 문제이다.

 

 

 

 

contest당시에는 이분 그래프에 대한 개념이 잘 잡혀있지 않아서 해결하지 못했었던 문제이다. 이후, 이분 그래프에 대해서 공부를 진행하고 해결할 수 있었다.

 

 

 

 

이분 그래프는 그래프의 모든 정점들을 두 가지 색으로 칠하려고 할 때, 인접한 모든 정점들끼리는 서로 다른 색으로 색칠할 수 있는 그래프이다.

 

 

 

 

이분그래프 예시

 

 

 

 

먼저 경우의 수를 나누어서 양방향 그래프를 완성시킨다.

• $i j \text{IMPOSTER}$ : $i$와 $j$는 임포스터 이므로, 두 정점 $i$와 $j$를 연결한다. 인접한 정점은 서로 다른 색으로 색칠하기 때문에 바로 연결한다.
• $i j \text{CREWMATE}$: $i$와 $j$는 서로 같은 팀이기 때문에, 두 정점 $i$와 $j$를 하나의 임시 정점을 사이에 두고 연결한다. 임시 정점을 두는 이유는 정점 $i$와 $j$를 같은 색으로 칠하기 위해서다.

 

 

 

 

완성된 그래프를 가지고, 이분 그래프인지 아닌지를 판별하는 과정을 거친다. 이분 그래프가 맞다면, 색칠된 정점들 중 더 많은 색의 개수가 임포스터의 수가 되며, 이분 그래프가 맞지 않다면 플레이어들이 말한 의견에 오류가 있는 것이다.

 

 

 

 

 

이제 이분 그래프인지 아닌지를 판별해야 하는데 그 방법은 DFS를 이용한 확인, BFS를 이용한 확인 2가지가 있다. 이번에 문제 해결을 위해서는 BFS로 해결하였다. 정점의 방문 여부는 색칠 여부로 확인을 진행했다.

 

 

 

 

1. 모든 정점을 흰색, 검은색으로 색칠한다 가정을 하고 아직 색칠되지 않은 정점 한 곳을 정해 흰색으로 칠한다.
2. 이후 연결된 정점들은 탐색하여 붙어있는 곳은 검은색으로 칠한다.
3. 다시 검은색과 인접한 아직 색칠되지 않은 정점들은 흰색으로 칠한다.
4. 2번으로 가서 다시 색칠하기를 진행한다. 더 이상 색칠할 곳이 없다면 종료한다.
5. 이미 색이 칠해진 곳에 그와 반대되는 색상을 칠해야 한다면 이분 그래프가 될 수 없기 때문에 바로 종료한다.

 

 

 

 

모든 정점들이 연결되어 있지 않을 수 있기 때문에 모든 정점을 순회하며 색칠되지 않은 정점이 없을 때까지 진행한다.

 

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#define MAX_PARTICIPANTS 200000
#define MAX_COMMENTS 500000
#define WHITE 0
#define BLACK 1
using namespace std;

int testcase;
int participants, comments;
int p1, p2, temp;
string impCrew;
int team[2];
int coloring[MAX_PARTICIPANTS + MAX_COMMENTS + 1];
vector<int> adj[MAX_PARTICIPANTS + MAX_COMMENTS + 1];
bool hasError = false;

void bfs(int here) {
    queue<pair<int, int>> q;
    q.push({here, WHITE});
    coloring[here] = WHITE;

    while(!q.empty()) {
        int cur = q.front().first;
        int color = q.front().second;
        q.pop();

        if (cur <= participants) team[color]++;

        int nextColor = color ^ (WHITE ^ BLACK);
        for (int there : adj[cur]) {
            if (coloring[there] == -1) {
                coloring[there] = nextColor;
                q.push({there, nextColor});
            } else if(coloring[there] != nextColor) {
                hasError = true;
                return;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> testcase;

    while (testcase--) {
        
        cin >> participants >> comments;

        // 초기화
        memset(coloring, -1, sizeof(coloring));
        hasError = false;
        for (int i = 0; i < participants + comments + 1; ++i) adj[i].clear();

        temp = participants + 1;
        while (comments--) {
            cin >> p1 >> p2 >> impCrew;
            if (impCrew == "imposter") {
                adj[p1].push_back(p2);
                adj[p2].push_back(p1);
            } else if (impCrew == "crewmate") {
                adj[p1].push_back(temp);
                adj[temp].push_back(p1);
                adj[p2].push_back(temp);
                adj[temp].push_back(p2);
                ++temp;
            }
        }

        int possibleImposter = 0;
        for (int i = 1; i <= participants && !hasError; ++i) {
            if (coloring[i] == -1) {
                team[WHITE] = team[BLACK] = 0;
                bfs(i);
                possibleImposter += max(team[WHITE], team[BLACK]);
            }
        }

        if (hasError) {
            cout << -1 << "\n";
        } else {
            cout << possibleImposter << "\n";
        }
    }

    return 0;
}

 

 

 

 

테스트 케이스마다 초기화를 진행할 때, 다음과 같이 모든 범위를 초기화시키려다 보니 시간 초과가 발생하였었다. 필요한 구간에 대해서만 초기화를 진행할 수 있도록 신경 써야 한다.

 

 

 

for (int i = 0; i < MAX_PARTICIPANTS + MAX_COMMENTS + 1; ++i) adj[i].clear(); // 시간초과
for (int i = 0; i < participants + comments + 1; ++i) adj[i].clear(); // OK

 

 

 

 

 

 

 

6. 문제 E1. Rubik's Cube Coloring (easy version) / solved

 

높이 h의 완전 이진트리가 있을 때, 각 노드들을 큐브 색으로 칠하려고 한다. 인접한 노드는 큐브에서 인접한 색상으로만 칠할 수 있으며, 같은 색으로도 칠할 수 없다.

• 루트 노드에 색칠할 수 있는 경우의 수 = 6
• 루트 노드를 제외한 나머지 노드에 색칠할 수 있는 경우의 수 = 4

 

 

 

 

위의 2가지만 생각하면 매우 간단하게 해결 가능한 문제이다.

 

#include <iostream>
#define MOD 1000000007

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int treeHeight; cin >> treeHeight;

    long long answer = 1;

    for (int i = 1; i < treeHeight; ++i) {
        answer = (answer * answer * 4) % MOD;
    }

    cout << (6 * answer * answer) % MOD << "\n";

    return 0;
}