hckim

풀이

• c 있는 위치 앞 뒤로 짝수개수 만큼 있으면 가능

코드

#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);
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);

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

        bool yes = false;

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == c && i % 2 == 0 && (s.size() - i - 1) % 2 == 0) {
                yes = true;
                break;
            }
        }

        if (yes) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

풀이

• l / a, r / a 가 같으면 r 일 때가 답
• 다르면 r 일 때의 몫 - 1 + 나머지부분은 a - 1 일 때와 r 값 중 최대

코드

#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 l, r, a;
        cin >> l >> r >> a;

        if (l / a == r / a) {
            cout << r / a + r % a << '\n';
        } else {
            cout << max(r / a + r % a, r / a - 1 + a - 1) << '\n';
        }
    }
}

풀이

• weight 작은 순서대로 2n 개 뽑고, x 좌표 정렬 후 각 segment 에 배정

코드

#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<long long> x(M), w(M);
        vector<tuple<long long, long long, long long> > v(M);
        for (int i = 0; i < M; ++i) {
            long long x, w;
            cin >> x >> w;
            v[i] = {x, w, i + 1};
        }
        sort(all(v), [&](tuple<long long, long long, long long> p1, tuple<long long, long long, long long> p2) {
            return get<1>(p1) < get<1>(p2);
        });
        sort(v.begin(), v.begin() + 2 * N, [&](tuple<long long, long long, long long> p1, tuple<long long, long long, long long> p2) {
            return get<0>(p1) < get<0>(p2);
        });

        long long ans = 0;
        for (int i = 0; i < 2 * N; ++i) {
            ans += get<1>(v[i]);
        }
        cout << ans << '\n';
        for (int i = 0; i < N; ++i) {
            cout << get<2>(v[i]) << ' ' << get<2>(v[2 * N - 1 - i]) << '\n';
        }
        cout << '\n';
    }
}

풀이

• 주어진 배열을 거꾸로 1, 2, ... 으로 만들자
• n 번째 수는 i = n shift 로, n -1 번째 수는 i = n - 1 shift 로 자리 잡는걸 끝내는게 최적

코드

• 시간복잡도: $O(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;
        deque<int> dq;
        for (int i = 0; i < N; ++i) {
            int num;
            cin >> num;
            dq.push_back(num);
        }

        vector<int> d(N);
        for (int i = N; i > 0; --i) {
            long long cnt = 0;
            while (dq.back() != i) {
                ++cnt;
                dq.push_back(dq.front());
                dq.pop_front();
            }
            d[i - 1] = cnt;
            dq.pop_back();
        }

        for (auto& e: d) {
            cout << e << ' ';
        }
        cout << '\n';
    }
}

풀이

• parametric search

코드

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

#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, D;
        cin >> N >> D;

        vector<tuple<long long, long long, long long> > a(N);
        vector<long long> pos2(N + 2);
        pos2[N + 1] = D + 1;
        pos2[0] = 0;
        long long last;
        for (int i = 0; i < N; ++i) {
            cin >> get<1>(a[i]);
            pos2[i + 1] = get<1>(a[i]);
            if (i == N - 1) last = get<1>(a[i]);
            if (i) get<0>(a[i]) = get<1>(a[i]) - get<1>(a[i - 1]) - 1;
            else get<0>(a[i]) = get<1>(a[i]) - 1;
            get<2>(a[i]) = i + 1;
        }
        sort(all(a));
        long long lo = 0, hi = D;
        auto check = [&](long long v) {
            vector<int> pos;
            for (auto [rest, p, idx]: a) {

                if (rest < v) {
                    pos.push_back(idx);
                }
            }
            if (pos.size() >= 3) return false;
            if (pos.size() == 2 && abs(pos.front() - pos.back()) != 1) return false;

            if (pos.size() == 2) {
                auto idx2 = min(pos.front(), pos.back());
                if (pos2[idx2 + 1] - pos2[idx2 - 1] - 1 < v) return false;

            }
            if (pos.size() == 1 && pos.front() >= 2 && pos2[pos.front()] - pos2[pos.front() - 2] - 1 >= 2 * v + 1) return true;
            if (pos.size() == 1 && pos.front() >= 1 && pos2[pos.front() + 1] - pos2[pos.front() - 1] - 1 >= 2 * v + 1) return true;
            if (pos.size() == 1 && pos.front() == N && D - pos2[pos.front() - 1] - 1 >= v) return true;
            if (get<0>(a.back()) >= 2 * v + 1 || D - pos2[N] >= v + 1) return true;
            if (pos.size() == 0) return true;
            return false;
        };
        while (lo + 1 < hi) {
            auto mid = lo + hi >> 1;
            if (check(mid)) lo = mid;
            else hi = mid;
        }

        cout << lo << '\n';
    }
}