hckim

풀이

• 배열 원소들의 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';
    }
}

풀이

• 극대점 다음 원소를 그 원소에 인접한 두 원소들 중 최대로 바꾸면 극대점을 최대 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';
    }
}

풀이

• $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';
            }
        }
    }
}

풀이

• 서로 다른 수로부터 생성되는 수들은 모두 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';
}

풀이

• 작은 수 + 1 == 큰 수 임을 체크한다.
• 작은 수 1 , 큰 수 10 케이스에 주의

코드

#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 a, b;
    cin >> a >> b;
 
    if (a > b) swap(a, b);
 
    if (a == 1 && b == 10) {
        cout << "Yes\n";
    } else if (a + 1 == b) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

풀이

• distinct 원소 개수 구하기
• set 에 insert

코드

• 시간복잡도: $O(NlogN)$

#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;
    cin >> N;
    set<int> s;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        s.insert(num);
    }
    cout << s.size() << '\n';
}

풀이

• $dp[i][j]: i$번 점프후 $j$위치에 있는 것이 가능하면 $1$ 아니면 $0$
• $dp[i][j] = 1$ 이면 $dp[i + 1][j + a[i + 1]] = dp[i + 1][j + b[i + 1]] = 1$

코드

• 시간복잡도: $O(NX)$

#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, X;
    cin >> N >> X;
 
    vector<vector<long long> > dp(N, vector<long long> (100 * 100 + 1, - 1));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        if (i == 0) {
            dp[i][a] = 1;
            dp[i][b] = 1;
            continue;
        }
        for (int j = 0; j <= 100 * 100; ++j) {
            if (dp[i - 1][j] == -1) continue;
            dp[i][j + a] = dp[i][j + b] = 1; 
        }
    }
 
    if (dp[N - 1][X] == 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

풀이

• 스택으로 {번호, 갯수} 를 관리
• top 과 같은 번호 들어오면 지울지 말지 결정
• 다른 번호들어오면 push

코드

#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;
    cin >> N;
 
    stack<pair<int, int> > st;
    int answer = 0;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
 
        if (st.size()) {
            if (st.top().first == num) {
                if (st.top().second == num - 1) {
                    st.pop();
                    answer -= num - 1;
                } else {
                    int tmp = st.top().second;
                    st.pop();
                    st.push({num, tmp + 1});
                    ++answer;
                }
            } else {
                st.push({num, 1});
                ++answer;
            }
        } else {
            st.push({num, 1});
            ++answer;
        }
        cout << answer << '\n';
    }
}

풀이

• dfs 하면서 리프 노드(간선이 부모랑밖에 없는 노드) 의 L = R = seq++
• 리프 노드가 아니면 자식노드들의 구간 모두 포함하게 구성

코드

• 시간복잡도: $O(N)$

#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;
    cin >> N;
    vector<vector<int> > adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> L(N + 1, 0), R(N + 1, 0);
    int seq = 1;
    function<void(int, int)> f = [&](int cur, int p) {
        if (adj[cur].size() == 1 && adj[cur][0] == p) {
            L[cur] = R[cur] = seq++;
            return;
        }
        int l = 1e9;
        int r = -1e9;
        for (auto e: adj[cur]) {
            if (e == p) continue;
            if (!L[e] && !R[e]) {
                f(e, cur);
            }
            l = min(l, L[e]);
            r = max(r, R[e]);
        }
        L[cur] = l;
        R[cur] = r;
    };
 
    f(1, 0);
    for (int i = 1; i <= N; ++i) {
        cout << L[i] << ' ' << R[i] << '\n';
    }
}

풀이

• 각 원소 반복의 끝, 또는 그 부분의 B 값이 양수이면 B 값이 음수 직전까지 의 A 값이 최대이다

코드

• 시간복잡도: $O(N)$

#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--) {
        long long N, M;
        cin >> N >> M;
        vector<pair<long long, long long> > C(N);
        vector<long long> A(N, -1e9), B(N, -1e9);
        for (int i = 0; i < N; ++i) {
            long long x, y;
            cin >> x >> y;
            C[i] = {x, y};
            B[i] = x * y;
            if (i) B[i] += B[i - 1];
            A[i] = x * y * (y + 1) / 2;
            if (i) A[i] += A[i - 1] + B[i - 1] * y;
        }
 
        long long answer = C[0].first;
        for (int i = 0; i < N; ++i) {
            if (i < N - 1 && C[i + 1].first < 0 && B[i] > 0) {
                long long k = B[i] / abs(C[i + 1].first);
                k = min(k, C[i + 1].second);
                answer = max(answer, A[i] + k * B[i] + k * (k + 1) * C[i + 1].first / 2);
            } else {
                answer = max(answer, A[i]);
            }
        }
        cout << answer << '\n';
    }
}

풀이

• 오름차순으로 되어있을 때 사전 순으로 맨 앞이다.
• 오름차순 정렬된 상태와 처음으로 같지 않을 때 그 위치에 있어야 할 수가 그 위치에 오도록 reverse 하지 않으면 그렇게 한 것보다 사전 순으로 뒤에 있다.
• 따라서 그 위치에 오도록 reverse 하는게 사전 순으로 맨 앞이다.

코드

• 시간복잡도: $O(N)$

#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;
        }
        vector<int> tmp(a);
        sort(all(tmp));
 
        for (int i = 0; i < N; ++i) {
            if (a[i] != i + 1) {
                auto it = find(a.begin() + i + 1, a.end(), i + 1);
                reverse(a.begin() + i, it + 1);
                break;
            }
        }
        for (auto& e: a) {
            cout << e << ' ';
        }
        cout << '\n';
    }
}

풀이

• 홀수, 짝수 사이는 자유롭게 스왑가능하다.
• 홀수, 홀수 이거나 짝수, 짝수 이면 스왑불가능하다.
• 따라서 operation 후 홀수들간의 위치관계 와 짝수들간의 위치관계는 각각 유지된다.
• 짝수, 홀수 들이 각각 정렬된 상태이면 전체를 정렬할 수 있다.

코드

• 시간복잡도: $O(N)$

#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> odd, even;
 
        for (int i = 0; i < N; ++i) {
            int num;
            cin >> num;
            if (num & 1) {
                odd.push_back(num);
            } else {
                even.push_back(num);
            }
        }
 
        if (is_sorted(all(odd)) && is_sorted(all(even))) {
            cout << "Yes\n";
        } else{
            cout << "No\n";
        }
    }
}

풀이

• Disjoint set 자료구조에서 각 셋의 최댓값을 루트로 한다.
• 배열 원소 차례로 순회하면서 이전 set 들의 최댓값들 중 지금 원소보다 큰 값이 있으면 union 한다.

코드

• 시간복잡도: 아마 $O(NlogN)$

※ 스택으로 연결된 그룹의 min, max 관리하면 $O(N)$ 으로 처리 가능

#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;
        }
 
        vector<int> p(N + 1, -1);
        function<int(int)> myFind = [&](int n) {
            if (p[n] == -1) return n;
            return p[n] = myFind(p[n]);
        };
        set<int> s;
        auto myUnion = [&](int n1, int n2) {
            int p1 = myFind(n1);
            int p2 = myFind(n2);
 
            if (p1 == p2) return;
            if (p1 > p2) swap(p1, p2);
            p[p1] = p2;
            s.erase(p1);
        };
 
        int answer = N;
        s.insert(a[0]);
        for (int i = 1; i < N; ++i) {
            auto it = s.upper_bound(a[i]);
            if (it != s.end()) {
                while (it != s.end()) {
                    myUnion(a[i], *it);
                    --answer;
                    it = s.upper_bound(myFind(a[i]));
                }
            } else {
                s.insert(a[i]);
            }
        }
        cout << answer << '\n';
    }
}

풀이

• 색칠순서를 역순으로 구성한다.
• 처음에는 4칸이 모두 같은색인 곳을 칠한다.
• 이전에 칠한곳은 지금칠할 곳을 덮어쓰므로 어떤색이어도 상관없다.
• 이전에 칠한곳 근처에서 4칸 중 이전에 칠한곳을 제외한 칸들이 모두 같은색이면 칠한다.

코드

• BFS
• 시간복잡도: $O(NM)$

#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, M;
    cin >> N >> M;
 
    vector<vector<int> > a(N, vector<int> (M));
    vector<vector<int> > b(N, vector<int> (M, 0));
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> a[i][j];
        }
    }
 
    queue<tuple<int, int, int> > q;
    auto check = [&](int i, int j) {
        if (i < 0 || i >= N - 1 || j < 0 || j >= M - 1) return 0;
        set<int> color;
        for (int ii = 0; ii < 2; ++ii) {
            for (int jj = 0; jj < 2; ++jj) {
                if (!b[i + ii][j + jj]) {
                    color.insert(a[i + ii][j + jj]);
                }
            }
        }
 
        if (color.size() == 1) {
            return *color.begin();
        } else {
            return 0;
        }
    };
 
    vector<vector<int> > visited(N - 1, vector<int> (M - 1, false));
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < M - 1; ++j) {
            auto c = check(i, j);
            if (c) {
                q.push({i, j, c});
                visited[i][j] = true;
            }
        }
    }
 
    vector<tuple<int, int, int> > answer;
    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    while (q.size()) {
        int cnt = q.size();
            auto [i, j, c] = q.front();
            q.pop();
            answer.push_back({i, j, c});
            b[i][j] = b[i + 1][j] = b[i][j + 1] = b[i + 1][j + 1] = true;
            for (int dir = 0; dir < 8; ++dir) {
                int ni = i + dr[dir];
                int nj = j + dc[dir];
                if (ni < 0 || ni >= N - 1 || nj < 0 || nj >= M - 1 || visited[ni][nj]) continue;
                auto nc = check(ni, nj);
                if (nc) {
                    q.push({ni, nj, nc});
                    visited[ni][nj] = true;
                }
            }
    }
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (!b[i][j]) {
                cout << "-1\n";
                return 0;
            }
        }
    }
 
    reverse(all(answer));
    cout << answer.size() << '\n';
    for (auto [i, j, c]: answer) {
        cout << i + 1 << ' ' << j + 1 << ' ' << c << '\n';
    }
}