Codeforces Round #765 A부터 B까지 업솔빙

Codeforces Round #765 A부터 B까지 업솔빙

C번 문제가 *1700문제라서 심지어 dp라 깔끔하게 포기하고 오는 길이다. 나는 *1400까지 문제만 깔끔하게 푸는 실력이 되고 싶다.

A. Ancient Civilization (*800)

접기/펼치기

문제 설명
이진수의 거리 는 다음과 같이 정의한다. 두 이진수끼리 같은 자리를 비교할 때, 서로 다른 숫자의 개수가 바로 그 거리이다.

$n$개의 이진수가 주어졌을 때, 각 이진수와 y사이 거리 합을 최소화 하는 이진수 $y$를 찾아라.

문제 해설
문제를 보면서 처음에는 단순하게 or연산을 사용하면 되나 싶었는데, 자세히 보니까 아니였다. $n$개의 이진수에 대해서 맨 뒤자리 비트부터 보는데, 각 자리의 비트에서 1의 개수와 0의 개수를 세고, 1의 개수가 많다면 그 자리에 1을 넣는다. 왜냐하면 개수가 많은 것과 같이 따라가야 다른 비트의 수가 작아지기 때문이다. 마찬가지로 0의 개수가 더 많다면 그 자리에 0을 넣으면 1을 넣는 것 보다 더 적은 거리를 만들 수 있다.

이 과정을 모든 비트에 대해서 수행하고 난 답을 출력하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, l; cin >> n >> l;
        int ans = 0, a[n];
        for(auto& x : a) cin >> x;
        for(int i = 0; i < l; i++){
            int cnt = 0;
            for(int j = 0; j < n; j++) cnt += ((a[j] >> i) & 1 == 1);
            if(cnt * 2 > n) ans |= (1 << i);
        }
        cout << ans << "\n";
    }
    return 0;
}

B. Elementary Particles (*1100)

접기/펼치기

문제 설명
$n$개의 수열 $(a_1, a_2, ..., a_n)$ 이 주어진다. 그리고 왼쪽 범위 $l$과 오른쪽 범위 $r$이 주어지고, 이 범위로 만든 부분 수열 $a_l, a_{l + 1}, ..., a_r$ 을 만든다.

우리가 구해야할 것은 두 부분 수열을 서로 조화롭게 만들어야 한다. 두 수열이 조화롭기 위해서는 해당 수열에 같은 index에 값이 하나라도 같으면 된다.

모든 두 조화로운 수열중에서 가능한 큰 수열의 길이를 출력하라.

문제 해설
브루트 포스 문제이다. 일단 $a_i$의 범위가 $150000$이기 때문에 모든 숫자의 개수를 셀 수 있다는 것이 이 문제의 핵심이다. 전체 수열에서 같은 숫자가 2개 이상 있으면 무조건 조화로운 수열을 만들 수 있다. 따라서 맨 처음부터 그리디하게 탐색을 시작하다가 이전에 본 숫자가 나오면 이전에 본 숫자의 왼쪽 길이 + 현재 본 숫자의 오른쪽 길이를 더한 값이 우리가 구하고 싶은 수열의 길이이다. 이 값중 최대값을 찾으면 되기 때문에 max함수를 사용해서 찾자.

그리디하게 탐색을 할때 같은 숫자 2개를 보고나서 그 뒤에 숫자가 나오면 맨 앞에 있는 숫자들은 필요가 없기 때문에 새로 갱신을 해도 상관이 없다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int cnt[150005] = {0, }, ans = -1;
        for(int i = 1; i <= n; i++){
            int a; cin >> a;
            if(cnt[a]) ans = max(ans, cnt[a] + n - i);
            cnt[a] = i;
        }
        cout << ans << "\n";
    }
    return 0;
}