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

풀이

• 인접한 땅과 땅사이 이동은 비용없이 가능
• 점프 단 한번 할 수 있는데 i, i + x 점프 비용 x
• 물 없으면 비용 0 으로 갈 수 있고 물이 있으면 점프를 첫부분과 연결된 땅의 오른쪽 끝에서 시작하여 , 끝부분과 연결된 땅의 왼쪽끝에서 도착하는 것이 최적이다.

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

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);
        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }

        int i = 0;
        while (i < N - 1) {
            if (a[i + 1] == 0) {
                break;
            }
            ++i;
        }
        if (i == N - 1) {
            cout << "0\n";
            continue;
        }

        int j = N - 1;

        while (j > 0) {
            if (a[j - 1] == 0) {
                break;
            }
            --j;
        }

        cout << j - i << '\n';
    }

}

풀이

• 패스 수 대로 배열 정렬
• 1, 2, 3, ... , n 번 그룹에서 n 번 공 가지고 출발해서 앞번호로 차례로 패스, n 번 마지막으로 공가져간다고 하면
• a[n] <= sum(a[1] ... a[n - 1]) 일 때 1개의 공으로 다 처리 가능,
  • 1번 0 될 때까지 1, ... n 그룹 패스
  • 2번 0 될 때까지 2, ... n 그룹 패스
• a[n]  이 클 때는 큰만큼 추가 공 필요

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

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 sum = 0;
        for (auto & e : a) {
            cin >> e;
            sum += e;
        }
        sort(all(a));
        if (a.back() == 0) {
            cout << "0\n";
            continue;
        }

        long long ans = 1;
        if (sum - a.back() < a.back()) {
            ans = a.back() - sum + a.back();
        }

        cout << ans << '\n';
    }
}

풀이

• 하나의 color 에 대해서
  • x 좌표들에 대해서
    • 그 x 좌표가 정답에 더해지는 부분은 그 좌표보다 작은 부분들 - 그 x 좌표 

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

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


    map<int, map<int, int> > mr;
    map<int, map<int, int> > mc;
    set<int> colors;
    int N, M;
    cin >> N >> M;


    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int c;
            cin >> c;
            colors.insert(c);
            ++mr[c][i];
            ++mc[c][j];
        }
    }

    long long ans = 0;
    for (auto c: colors) {
        long long tmp = 0;
        long long tmpCnt = 0;
        for (auto it = mr[c].begin(); it != mr[c].end(); ++it) {
            ans += (it -> first * tmpCnt - tmp) * it -> second;
            tmp += it -> first * it -> second;
            tmpCnt += it -> second;
        }

        tmp = 0;
        tmpCnt = 0;
        for (auto it = mc[c].begin(); it != mc[c].end(); ++it) {
            ans += (it -> first * tmpCnt - tmp) * it -> second;
            tmp += it -> first * it -> second;
            tmpCnt += it -> second;
        }
    }
    cout << ans << '\n';    
}

풀이

• 몫의 범위는 0 ~ C
• 지금 배열안에 존재하지 않는 값에 대하여, 그 값이 몫으로 나올 수 있는지 체크
• 모든 배열 원소에 대하여, 원소 값을 x 라 하면, x * c ~ x * (c + 1) 사이에 값이 있으면 몫으로 그 값이 나올 수 있겠다.
• c 는 0~C 까지 돌려야되고 x 는 x * c <= C 까지만 돌려도 되므로
• 시간 복잡도 계산은 C + C/ 2 + C / 3 ...  = ClogC

코드

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

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

        vector<int> exist(C + 1, false);
        vector<int> a(N);
        for (auto& e: a) {
            cin >> e;
            exist[e] = true;
        }

        vector<int> pe(C + 1, 0);
        for (int i = 1; i < C + 1; ++i) {
            pe[i] = pe[i - 1] + exist[i];
        }

        bool yes = true;
        for (int i = 1; i <= C; ++i) {
            if (exist[i]) continue;
            for (int j = 1; j * i <= C; ++j) {
                if (!exist[j]) continue;
                // i not exist, j exist, check exist something / j = i
                if (pe[min(C, j * (i + 1) - 1)] - pe[j * i - 1]) {
                    yes = false;
                    break;
                }
            }
            if (!yes) break;
        }

        if (yes) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

풀이

• j = 0 ... i -1 에서 s[j] = t[j] 이고, s[i] < t[i] 인 개수 를 i가 0 ... m 일 때 더해주면 답이다.

코드

#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);

    long long N, M;
    cin >> N >> M;

    vector<long long> s(N), t(M);
    vector<long long> t2(2 * 200001, 0);
    vector<long long> fact(200001, 1LL);
    long long MOD = 998244353;
    for (long long i = 1; i < fact.size(); ++i) {
        fact[i] = i * fact[i - 1] % MOD;
    }

    auto fpow = [&](long long base, long long p) {
        long long ret = 1;
        while (p) {
            if (p & 1) {
                ret = ret * base % MOD;
            }
            base = base * base % MOD;
            p >>= 1;
        }
        return ret;
    };

    int n = 200001;
    long long div = 1;

    for (auto& e: s) {
        cin >> e;
        ++t2[n + e];
    }

    for (long long i = 1; i <= 200000; ++i) {
        if (t2[n + i]) {
            div = div * fpow(fact[t2[n + i]], MOD - 2) % MOD;
        }
    }

    for (auto& e: t) {
        cin >> e;
    }

    for (int i = n - 1; i >= 1; --i) {
        t2[i] = t2[i << 1] + t2[i << 1 | 1];
    }

    auto query = [&](int l, int r) {
        long long ret = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += t2[l++];
            if (r & 1) ret += t2[--r];
        }
        return ret;
    };

    auto update = [&](int p, int val) {
        for (t2[p += n] = val; p > 1; p >>= 1) t2[p >> 1] = t2[p] + t2[p ^ 1];
    };

    long long ans = 0;
    for (int i = 0; i < M; ++i) {
        ans += div * fact[N - i - 1] % MOD * query(0, t[i]) % MOD;
        ans %= MOD;

        if (t2[n + t[i]]) {
            div = div * t2[n + t[i]] % MOD;
            update(t[i], t2[n + t[i]] - 1);
        } else {
            if (i >= N) ans += 1, ans %= MOD;
            break;
        }
    }
    cout << ans << '\n';
}

풀이

• n + 1 개 중 $a[i] = n^2 $인 원소의 개수를 x 라 하면
• $s = x * n^2 + R$ 이고 $R = (n + 1 - x) * (0...n - 1)$ 이다
• R 의 최대가 $n^2 - 1$ 이므로 
• 구하는 답은 $ S / 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--) {
        long long N, S;
        cin >> N >> S;

        cout << S / (N * N) << '\n';
    }
}

풀이

• 빨간색 개수보다 파란색 개수가 한개 더 많은 것이 개수 조건을 만족하면서, 합조건을 만족하기에 최선이다.
• 파란색 집합에는 작은것, 빨간색 집합에는 큰것이 들어가는 것이 합조건을 만족하기에 최선이다.
• 배열 오름차순 정렬후 파란색을 앞에서부터, 빨간색을 뒤에서부터 개수 증가시켜가면서 조건 만족하는 것 있는지 찾기

코드

• 시간복잡도: $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 TC; cin >> TC;
    while (TC--) {
        int N;
        cin >> N;
        vector<long long> a(N), pa(N, 0);
        for (int i = 0; i < N; ++i) {
            cin >> a[i];
        }
        sort(all(a));
        for (int i = 0; i < N; ++i) {
            pa[i] = a[i];
            if (i) pa[i] += pa[i - 1];
        }
        

        bool yes = false;
        for (int i = 2; i < N; ++i) {
            if (i + i - 1 > N) break;
            if (pa[i - 1] < pa[N - 1] - pa[N - i]) {
                yes = true;
                break;
            }
        }

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

풀이

• powerful number 는 겹치지 않는 두 집합으로 나눌 수 있다.
  • $2^d$ : $1, 2, 4, 8, ... $
  • $3!, 4!, 5!, ...$
• $10^{12}$ 를 넘지 않는 팩토리얼은 $14!$ 이므로 모든 조합의 수는 $2^{12} - 1$ 이다.
• N 넘지 않는 모든 팩토리얼 합에 대해서 개수를 구해주고 최소를 구하면 된다.

코드

• 시간복잡도: $O(2^{12})$

#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);

    vector<long long> fac(15, 1);
    for (int i = 1; i < 15; ++i) {
        fac[i] = fac[i - 1] * i;
    }
    
    int TC; cin >> TC;
    while (TC--) {
        long long N;
        cin >> N;
        long long ans = 1e9;
        for (long long i = 0; i < (1 << 12); ++i) {
            long long cnt1 = 0, cnt2 = 0;
            long long factSum = 0;

            for (long long j = 0; j < 12; ++j) {
                if (i & (1LL << j)) {
                    factSum += fac[j + 3];
                    ++cnt1;
                }
            }

            long long tmp = N - factSum;
            if (tmp < 0) break;
            while (tmp) {
                if (tmp & 1) ++cnt2;
                tmp >>= 1;
            }

            ans = min(ans, cnt1 + cnt2);
        }
        cout << ans << '\n';
    }
}

풀이

• N = 2 인 경우를 제외하고, 한 간선의 양 끝 정점이 모두 good 일 수 없다.
• not good 일 때는 value 가 1 일 때 최소 합을 가진다.
• $dp[i][g]: $ i 정점이 good: g 이고 i 루트로 가지는 서브트리의 {최대 good 개수, 최소 합} 으로 정의
• $dp[i][g]$ 를 구할 때 g 가 true 이면( good 이면) 그 아래 정점들은 무조건 not good 이지만, g 가 false 면 그 아래 정점들이 good, not good 두가지 모두 따져야 원하는 dp 값을 구할 수 있다.

코드

• 시간복잡도:$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;

    if (N == 2) {
        cout << "2 2\n";
        cout << "1 1\n";
        return 0;
    }
    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<vector<pair<int, int> > > dp(N + 1, vector<pair<int, int> > (2, {-1, -1}));
    function<pair<int, int>(int, int, int)> f = [&](int cur, int g, int p) {
        auto& ret = dp[cur][g];

        if (ret.first != -1) {
            return ret;
        }

        if (g) {
            ret = {g, -adj[cur].size()};
            for (auto e: adj[cur]) {
                if (e == p) continue;
                ret.first += f(e, !g, cur).first;
                ret.second += f(e, !g, cur).second;
            }
        } else {
            // not good
            ret = {g, -1};
            for (auto e: adj[cur]) {
                if (e == p) continue;
                if (f(e, g, cur) > f(e, !g, cur)) {
                    ret.first += f(e, g, cur).first;
                    ret.second += f(e, g, cur).second;
                } else {
                    ret.first += f(e, !g, cur).first;
                    ret.second += f(e, !g, cur).second;
                }
            }
        }

        return ret;
    };

    auto ans = max(f(1, 1, -1), f(1, 0, -1));

    cout << ans.first << ' ' << -ans.second << '\n';
    
    vector<int> w(N + 1, 0);
    function<void(int, int, pair<int, int>)> f2 = [&](int cur, int p, pair<int, int> val) {
        if (val == f(cur, 0, p)) {
            w[cur] = 1;
            for (auto e: adj[cur]) {
                if (e == p) continue;
                f2(e, cur, max(f(e, 0, cur), f(e, 1, cur)));
            }
        } else {
            w[cur] = adj[cur].size();
            for (auto e: adj[cur]) {
                if (e == p) continue;
                f2(e, cur, f(e, 0, cur));
            }
        }

    };
    f2(1, -1, ans);
    for (int i = 1; i <= N; ++i) {
        cout << w[i] << ' ';
    }
    cout << '\n';
}

풀이

• $x, x^2, ... , x^k$ 행들에서만 중복이 나올 수 있다. k 는 최대 $log_2 N$
• 각 행의 지수들은
  • $1 * 1, 1 * 2, ..., 1 * M$
  • $2 * 1, 2 * 2, ..., 2 * M$
  • $k * 1, k * 2, ..., k * M$
• k 에 따라 이 set 들에서의 distinct 한 개수가 정해진다.

코드

• 시간복잡도: $O(MlogN + 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, M;
    cin >> N >> M;

    vector<long long> cnt(log2(N) + 1, 0);
    vector<long long> checked((long long)(cnt.size()) * M, false);
    long long ccnt = 0;
    for (long long i = 1; i < cnt.size(); ++i) {
        for (long long j = 1; j <= M; ++j) {
            if (checked[i * j]) continue;
            checked[i * j] = true;
            ++ccnt;
        }
        cnt[i] = ccnt;
    }

    long long ans = 1;
    vector<int> counted(N + 1, false);
    for (long long i = 2; i <= N; ++i) {
        if (counted[i]) continue;

        long long tmp = i;
        long long k = 0;
        while (tmp <= N) {
            ++k;
            counted[tmp] = true;
            tmp *= i;
        }

        ans += cnt[k];
        counted[i] = true;
    }
    cout << ans << '\n';
}