[코드포스] Codeforces Round #772 (Div. 2) 풀이

https://codeforces.com/contest/1635

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

 

A. Min Or Sum

풀이

• 배열 원소들의 or 값은 일정
• 0 아닌 두 수를 0 과 $a_i$ $|$ $a_j$ 로 바꾸자

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<long long> a(N);
        long long answer = 0;
        for (auto& e: a) {
            cin >> e;
            answer |= e;
        }
        cout << answer << '\n';
    }
}

 

B. Avoid Local Maximums

풀이

• 극대점 다음 원소를 그 원소에 인접한 두 원소들 중 최대로 바꾸면 극대점을 최대 2개까지 없앨 수 있다

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<int> a(N);
        for (auto& e: a) {
            cin >> e;
        }
 
        int answer = 0;
        for (int i = 1; i < N - 1; ++i) {
            if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                if (i == N - 2) a[i + 1] = a[i], ++answer;
                else a[i + 1] = max(a[i], a[i + 2]), ++answer;
            }
        }
 
        cout << answer << '\n';
        for (auto& e: a) {
            cout << e << ' ';
        }
        cout << '\n';
    }
}

 

C. Differential Sorting

풀이

• $x$ 최대가 $N - 2$ 이므로 $a_{N - 1} <= a_{N}$ 이어야 함 아니면 불가능
• 뒤의 두개가 정렬된 상태일 때
  • $a_N >= 0$ 이면 $a_{N - 1} - a_{N} <= a_{N - 1} <= a_{N}$ 성립
    • 나머지를 다 $a_{N - 1} - a_{N}$ 으로 바꿈
  • $a_N < 0$ 이면 모두 정렬된 상태가 아니면 불가능함
    • operation 후 정렬된 상태라면 모두 음수인데 음수에 대해서 정렬된 상태로 만들 수 없음

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<long long> a(N);
        for (auto& e: a) {
            cin >> e;
        }
 
        bool no = false;
 
        vector<tuple<int, int, int> > answer;
        if (a[N - 2] > a[N - 1]) {
            no = true;
        } else if (a[N - 1] >= 0) {
            for (int i = 0; i + 2 < N; ++i) {
                answer.push_back({i + 1, N - 1, N});
            }
        } else {
            if (!is_sorted(all(a))) {
                no = true;
            }
        }
 
        if (no) {
            cout << "-1\n";
        } else {
            cout << answer.size() << '\n';
            for (auto [x, y, z]: answer) {
                cout << x << ' ' << y << ' ' << z << '\n';
            }
        }
    }
}

 

D. Infinite Set

풀이

• 서로 다른 수로부터 생성되는 수들은 모두 distinct 함
• $f(x) = k, 2^k <= x <= 2^{k + 1}$ 라고할 때
  • $f(2x + 1) = k + 1$ 이고 $f(4x) = k + 2$ 이다.
• 최초 배열에서 제일 근본적인 수만 남기고 그 원소들에 대해서 dp (최소 스패닝)

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N, P;
    cin >> N >> P;
 
    set<int> s;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        s.insert(num);
    }
 
    vector<int> v;
    for (auto it = s.rbegin(); it != s.rend(); ++it) {
        bool del = false;
        auto tmp = *it;
        while (tmp > 0) {
            if (tmp != *it && s.count(tmp)) {
                del = true;
                break;
            }
            if (tmp & 1) {
                tmp >>= 1;
            } else if (tmp % 4 == 0) {
                tmp >>= 2;
            } else {
                break;
            }
        }
        if (!del) {
            v.push_back(*it);
        }
    }
    reverse(all(v));
    vector<long long> dp(P, 0);
    for (long long tmp = 1, i = 0; i < P && tmp <= v.back(); ++i, tmp <<= 1LL) {
        dp[i] += lower_bound(all(v), tmp * 2) - lower_bound(all(v), tmp);
    }
 
    long long MOD = 1e9 + 7;
    long long answer = 0;
    for (int i = 0; i < P; ++i) {
        if (i + 1 < P) dp[i + 1] += dp[i], dp[i + 1] %= MOD;
        if (i + 2 < P) dp[i + 2] += dp[i], dp[i + 2] %= MOD;
        answer += dp[i];
        answer %= MOD;
    }
 
    cout << answer << '\n';
}