1083번: 소트

https://www.acmicpc.net/problem/1083

가능한 한 큰 수가 앞에 오도록 만든다.

시간복잡도는 테스트케이스마다 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s, a[50];
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        scanf("%d", &s);
        for (int i = 0; i < n; i++) {
            int p = max_element(a + i, a + min(s + i + 1, n)) - a;
            rotate(a + i, a + p, a + p + 1);
            s -= p - i;
        }
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}

14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

https://www.acmicpc.net/problem/14698

현재 남아 있는 가장 작은 에너지를 가진 두 슬라임의 합성을 반복한다.

ei: i번 슬라임의 에너지
c(i): i번 슬라임에 의해 최종적으로 비용에 ei가 곱해진 횟수
어떤 시점에서 에너지가 작은 순으로 슬라임에 번호를 매겼다고 하자.
그러면 c(i)는 단조 감소 함수가 된다.
만약 어떤 x, y에 대해 c(x)<c(y) & x<y를 만족한다면 x, y번 슬라임을 바꿔 조합해서 더 작은 비용을 만들 수 있으므로 모순이 생기기 때문이다.

이제 t(>2)번 슬라임이 2번 슬라임보다 빨리 1번 슬라임과 합성했다고 하자.
그러면 c(t)=c(1)
세 슬라임에 의해 비용에 곱해진 값은 e1^c(1) * e2^c(2) * et^c(1) ... (1)
여기서 2번 슬라임과 t번 슬라임을 바꿔서 조합했다면 곱해진 값은
e1^c(1) * e2^c(1) * et^c(2) ... (2) (* 여기서 c(x)는 처음 방법에 대한 값임)
c(1) >= c(2), et >= e2 이므로
(1) / (2) = (et / e2)^{c(1)-c(2)} >= 1
따라서 (2)의 방법이 (1)의 방법보다 나쁘지 않다. 결과적으로 1, 2번 슬라임을 먼저 합성해도 최소 비용을 구할 수 있다.

시간복잡도는 테스트케이스마다 $O(n\lg n)$

#include<cstdio>
#include<queue>
#define mod int(1e9+7)
using namespace std;
int t, n;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        priority_queue<long long> pq;
        long long c, t;
        while (n--) scanf("%lld", &c), pq.push(-c);
        int res = 1;
        while (pq.size() > 1) {
            t = pq.top(); pq.pop();
            t *= pq.top(); pq.pop();
            res = t%mod*res%mod;
            pq.push(-t);
        }
        printf("%d\n", res);
    }
    return 0;
}

5842번: Partitioning the Farm

https://www.acmicpc.net/problem/5842

먼저 가로 방향 울타리의 위치를 정한다. 여기서 가능한 모양의 경우의 수는 $2^{n-1}$일 것이다.
그 다음, 남은 울타리를 세로 방향으로 설치하되 그룹 안 소의 최대 수가 최소가 되도록 설치하는 법을 찾아야 한다.
그룹 안 소의 최대 수를 x라고 하고 이 값에 대해 파라메트릭 서치를 한다. 농장의 왼쪽 열부터 보면서 그룹 안 소의 최대 수가 x이하가 되도록 세로로 울타리를 세웠을 때 모든 울타리 수가 k개 이하인지 판단하는 문제로 바꿔 풀 수 있다.

시간복잡도는 $O(2^{n/2}*n^2*\lg L)$

#include<cstdio>
int n, k, s[16][16], a[16], sz, mid, res = 1e9;
bool f() {
    int t = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sz; j++) while (s[a[j]][i] - s[a[j]][t] - s[a[j - 1]][i] + s[a[j - 1]][t] > mid) {
            if (t == i - 1) return false;
            t = i - 1, cnt++;
        }
    }
    return cnt <= k - sz + 1;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        scanf("%d", s[i] + j);
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
    for (int i = 1 << n - 1; i--;) {
        sz = 0;
        for (int j = 0; j < n - 1; j++) if (1 << j&i) a[++sz] = j + 1;
        a[++sz] = n;
        int low = 0, up = 1e6;
        while (low <= up) {
            mid = low + up >> 1;
            f() ? up = mid - 1 : low = mid + 1;
        }
        if (res > up) res = low;
    }
    printf("%d", res);
    return 0;
}

5888번: Haybale Restacking

https://www.acmicpc.net/problem/5888

#include<cstdio>
#include<cstdlib>
int s[100001], n;
long long f(int x) {
    long long ret = 0;
    for (int i = 1; i <= n; i++) ret += abs(s[i] - x);
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        s[i] = s[i - 1] + y - x;
    }
    int low = 0, up = 2e8, mid;
    while (low < up) {
        mid = low + up >> 1;
        f(mid - 1e8) < f(mid - 1e8 + 1) ? up = mid : low = mid + 1;
    }
    printf("%lld", f(up - 1e8));
    return 0;
}

13164번: 행복 유치원

https://www.acmicpc.net/problem/13164

i번째 원생의 키를 a[i]라 하자.
a[i]-a[i-1]이 가장 작은 n-k개의 i에 대해 i-1번째 원생과 i번째 원생을 같은 조에 속하도록 만든다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, a[300000], s;
int main() {
    scanf("%d%d%d", &n, &k, a);
    for (int i = 1; i < n; i++) scanf("%d", a + i), a[i - 1] = a[i] - a[i - 1];
    sort(a, a + n - 1);
    for (int i = 0; i < n - k; i++) s += a[i];
    printf("%d", s);
    return 0;
}

3119번: OGRADA

https://www.acmicpc.net/problem/3119

높이가 h 이상인 나무판에 대해 남는 여부를 결정했다면 해당 나무판들은 최종적으로 남아있을 수 있다.
높이가 h 미만인 나무판들로 어떠한 울타리를 만들어도 높이가 h 이상인 나무판을 포함할 수 없기 때문이다.

그러므로 다음의 그리디 알고리즘이 가능하다.
1. 현재 남아있을지 결정해야 하는 나무판들의 높이 중 최댓값을 h라 한다.
2. 높이가 h인 나무판들에 대해 이미 남아 있기로 결정된 h보다 큰 나무판과 겹치는 부분을 제거한다. 높이가 h인 각 나무판마다 제거되지 않은 부분의 x 성분 최솟값을 si, 최댓값을 ei 라 하자.
3. i < j일 때 si < sj & ei < ej를 만족하도록 높이가 h인 나무판들을 최대한 많이 선별한다.
4. 선별된 나무판들을 최종적으로 남도록 결정한다.
5. 결정하지 못한 나무판들에 대해 1로 돌아가 처리한다.

2, 3번 과정은 map으로 처리 가능하다. 자세한 구현은 아래 소스를 참고하자.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int n;
struct st { int x, w, h, idx; }a[100000];
vector<int> res;
vector<pair<int, int> > stk;
map<int, int> mp;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].h), a[i].idx = i + 1;
    sort(a, a + n, [](st i, st j) {return i.h > j.h || i.h == j.h&&i.x < j.x; });
    for (int i = 0, s, e; i < n; i++) {
        auto it = mp.upper_bound(s = a[i].x);
        if (it != mp.begin() && s < (--it)->second) s = it->second;
        it = mp.upper_bound(e = a[i].x + a[i].w);
        if (it != mp.begin() && e <= (--it)->second) e = it->first;
        if (s < e && (stk.empty() || stk.back().second < e)) {
            while (!stk.empty() && stk.back().first == s) stk.pop_back(), res.pop_back();
            stk.push_back({ s,e });
            res.push_back(a[i].idx);
        }
        if (i == n - 1 || a[i].h^a[i + 1].h) {
            while (!stk.empty()) {
                s = stk.back().first;
                e = stk.back().second;
                it = mp.upper_bound(s);
                if (it != mp.begin() && s == prev(it, 1)->second) s = (--it)->first;
                while (it != mp.end() && it->first <= e) {
                    e = max(e, it->second);
                    mp.erase(it++);
                }
                mp[s] = e;
                stk.pop_back();
            }
        }
    }
    printf("%d\n", res.size());
    for (auto it : res) printf("%d ", it);
    return 0;
}

9446번: Dwarf Tower

https://www.acmicpc.net/problem/9446

1. 다익스트라 알고리즘을 응용해서 풀 수 있다.
2. 현재까지 최소 비용을 구한 아이템 집합을 S라 하자.
3. 초기에는 제작 비용이 가장 싼 아이템이 S에 포함되어있다.
4. S이외의 아이템을 S로부터 제작 혹은 구매를 할 때 최소 비용과 해당 아이템을 각각 c, p라고 하자.
5. 앞으로 어떠한 방법을 사용해도 비용은 c보다 작을 수 없으므로 p를 만들기 위한 최소 비용은 c이다. 이 t를 S에 포함시킨다.
6. 이 그리디 알고리즘을 반복하면 각각의 아이템를 얻기위한 최소 비용을 모두 구할 수 있다.

시간복잡도는 $O((m+n)\lg(m+n))$

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, m, cost[10001];
priority_queue<pair<int, int> > pq;
vector<pair<int, int> > v[10001];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", cost + i), pq.push({ -cost[i],i });
    for (int i = 0, a, x, y; i < m; i++) {
        scanf("%d%d%d", &a, &x, &y);
        v[x].push_back({ y,a });
        v[y].push_back({ x,a });
    }
    while (!pq.empty()) {
        int c = -pq.top().first, p = pq.top().second;
        pq.pop();
        if (cost[p] ^ c) continue;
        cost[p] = c;
        for (auto it : v[p]) if (cost[it.second]>c + cost[it.first]) {
            cost[it.second] = c + cost[it.first];
            pq.push({ -cost[it.second],it.second });
        }
    }
    printf("%d", cost[1]);
    return 0;
}

2831번: PLES

https://www.acmicpc.net/problem/2831

$O(n\lg n)$

각 큰 키를 요구하는 사람에 대해 해당 사람과 춤을 출 수 있는 사람 중 가장 작은 키의 사람과 매칭시킨다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, r;
vector<pair<int, int> > p[2];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        x < 0 ? p[1].push_back({ -x,0 }) : p[0].push_back({ x,1 });
    }
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        x < 0 ? p[0].push_back({ -x,0 }) : p[1].push_back({ x,1 });
    }
    sort(p[0].begin(), p[0].end());
    sort(p[1].begin(), p[1].end());
    for (int i = 0; i < 2; i++) {
        int c = 0;
        for (auto it : p[i]) {
            if (it.second) c++;
            else if (c) c--, r++;
        }
    }
    printf("%d", r);
    return 0;
}

1785번: 보드 게임

https://www.acmicpc.net/problem/1785


$O((\log n)^4)$

주어진 방법으로 지폐단위를 만들면 큰 지폐 단위부터 순서대로 최대한 환전했을 때 필요한 지폐 총 개수가 최소가 된다.
이러한 특성을 이용하여 다음 점화식을 통해 DP를 한다.

dp[i][j][k][l]: 2,3,4,5를 각각 i,j,k,l번 곱해 나온 지폐 단위 + 이후 만든 더 큰 지폐 단위를 이용하여 나머지를 최소화하며 환전할 때 필요한 최소 지폐 수
p = 2^i * 3^j * 4^k * 5^l이면
dp[i][j][k][l] = min(
dp[i+1][j][k][l] + n/p%2,

dp[i][j+1][k][l] + n/p%3,

dp[i][j][k+1][l] + n/p%4,

dp[i][j][k][l+1] + n/p%5)

답은 dp[0][0][0][0]

#include<cstdio>
#include<algorithm>
using namespace std;
long long n, dp[60][38][30][26];
int k, c[6];
long long f(long long x, int y) {
    if (!x || !y) return x;
    long long &ret = dp[c[2]][c[3]][c[4]][c[5]];
    if (ret) return ret;
    ret = 1e18;
    for (int i = 2; i <= 5; i++) {
        c[i]++;
        ret = min(ret, x%i + f(x / i, y - 1));
        c[i]--;
    }
    return ret;
}
int main() {
    scanf("%lld %d", &n, &k);
    printf("%lld", f(n, k - 1));
    return 0;
}

14552번: Mahjong

https://www.acmicpc.net/problem/14552

$O(...)$

x삭이 대기패인지는 다음 경우들을 조사해서 알 수 있다.
1. x삭이 이미 4개면 불가능하다.
2. x삭을 포함해 같은 삭 쌍이 7개인지 조사(같은 패로 두 쌍은 제외)
3. x삭을 포함해 머리 1개 몸통 4개를 만들 수 있는지 조사

2번은 간단히 for-loop를 통해 확인할 수 있다.

3번은 각 숫자 패마다 머리로 가정하고 몸통 4개가 가능한지 그리디 알고리즘으로 따져볼 수 있다.
기존 패에서 x삭을 추가, 머리로 가정한 한 쌍의 패를 제거한 세트가 주어졌다고 하자.
작은 i부터 보며
i-2, i-1, i번 패가 모두 한 장이상 존재하면 이들로 가능한 만큼의 몸통을 만들고
이후 i번 패가 세 장 이상 존재하면 이들로 몸통을 만든다.
이렇게 해서 만든 몸통이 4개면 x삭은 대기패이다.

#include<cstdio>
int c[10], ck;
bool f() {
    int cnt = 0;
    for (int j = 1; j <= 9; j++) if (c[j] == 2) cnt++;
    if (cnt == 7) return true;
    for (int j = 1; j <= 9; j++) if (c[j] > 1) {
        int t[10], cnt = 0;
        for (int k = 1; k <= 9; k++) t[k] = c[k];
        t[j] -= 2;
        for (int k = 1; k <= 9; k++) {
            while (k > 2 && t[k - 2] && t[k - 1] && t[k]) t[k - 2]--, t[k - 1]--, t[k]--, cnt++;
            if (t[k] > 2) t[k] -= 3, cnt++;
        }
        if (cnt == 4) return true;
    }
    return false;
}
int main() {
    for (int i = 1, x; i <= 13; i++) scanf("%d", &x), c[x]++;
    for (int i = 1; i <= 9; i++) if (c[i] < 4) {
        c[i]++;
        if (f()) printf("%d ", i), ck = 1;
        c[i]--;
    }
    if (!ck) puts("-1");
    return 0;
}

1432번: 그래프 수정

https://www.acmicpc.net/problem/1432

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, ind[300], res[300];
vector<int> adj[300];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0, x; j < n; j++) {
            scanf("%1d", &x);
            if (x) adj[j].push_back(i), ind[i]++;
        }
    }
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) if (!ind[i]) pq.push(i);
    int m = n;
    while (!pq.empty()) {
        int h = pq.top();
        pq.pop();
        res[h] = m--;
        for (auto it : adj[h])
            if (!--ind[it]) pq.push(it);
    }
    if (m) puts("-1");
    else for (int i = 0; i < n; i++) printf("%d ", res[i]);
    return 0;
}

2012번: 등수 매기기

https://www.acmicpc.net/problem/2012


$O(n\lg n)$

예상 번호를 기준으로 오름차순 정렬하고 각 인덱스를 해당 학생의 등수로 지정한다.

이 방법이 최적임은 증명해보자.
최적해에서 i<j이고 ai>aj인 경우가 존재한다고 가정하면
항상 |ai-i|+|aj-j| >= |ai-j|+|aj-i|이다.
그래서 aj, ai 순으로 등수를 매기면 적어도 이전보다 불만도가 커지지는 않는다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[500001];
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) r += abs(a[i] - i);
    printf("%lld", r);
    return 0;
}

5545번: 最高のピザ (Best Pizza)

https://www.acmicpc.net/problem/5545

$O(n\lg n)$

토핑의 열량이 큰 것부터 보며 올렸을 때 1달러 당 열량이 증가하는 것만 올리면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a, b, c, x[100];
int main() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 0; i < n; i++) scanf("%d", x + i);
    sort(x, x + n);
    for (int i = n; i--;) if (b*c < a*x[i]) c += x[i], a += b;
    printf("%d", c / a);
    return 0;
}

6233번: Face The Right Way

https://www.acmicpc.net/problem/6233


$O(n^2)$

임의의 k에 대해 기계의 최소 작동 횟수는 그리디 알고리즘을 통해 O(n)에 구할 수 있다.

k가 정해지면 앞의 소부터 보면서 뒤돌아 있는 경우 그 뒤 k마리의 방향을 바꿔주면 된다. 이를 빠르게 처리하기 위해 prefix sum과 비슷하게 기계의 누적 작동횟수와 이후 기계가 작동을 멈출 시점을 저장해준다.

#include<cstdio>
int n, k, m = 1e9;
char d[5000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf(" %c", d + i);
    for (int i = 1; i <= n; i++) {
        int cnt = 0, t = 0, j = 0, s[5001] = {};
        for (; j < n; j++) if ((t ^= s[j]) ^ d[j] == 'B') {
            if (j + i>n) break;
            cnt++;
            t ^= 1;
            s[j + i]++;
        }
        if (j == n && m>cnt) m = cnt, k = i;
    }
    printf("%d %d", k, m);
    return 0;
}

1161번: Fair Shuttle

https://www.acmicpc.net/problem/1161

참고로 어떤 그룹에서 일부만 버스에 타도 괜찮다.

$O(nc\lg c)$

(s,e,m)이 주어져 있을 때, [s,e] 스케줄이 m개 있다고 생각하자.
그러면 유명한 스케줄링 알고리즘을 응용해서 풀 수 있다.

먼저, 도착지점을 기준으로 오름차순으로 정렬한다.
앞으로 최대 c개의 끝지점의 위치를 가지고 다닐 것이다. 이러한 위치를 a1<a2<...<ac라고 하자.
구간 [s,e]가 보았을 때 ai<=s를 만족하는 최대 ai가 존재할 경우 해당 구간을 스케줄에 집어 넣을 수 있다.
이제 ai를 e로 대체하고 수열을 오름차순으로 유지하며 앞의 행위를 반복한다.

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct scd {
    int s, e, m;
}sg[50000];
multiset<int> st;
int k, n, c, res;
int main() {
    scanf("%d%d%d", &k, &n, &c);
    for (int i = 0; i < k; i++) scanf("%d%d%d", &sg[i].s, &sg[i].e, &sg[i].m);
    sort(sg, sg + k, [](scd u, scd v) {
        return u.e < v.e;
    });
    for (int i = 0; i < c; i++) st.insert(0);
    for (int i = 0; i < k; i++) {
        auto it = st.lower_bound(-sg[i].s);
        int cnt = 0;
        while (it != st.end() && cnt < sg[i].m) {
            st.erase(it++);
            cnt++;
        }
        res += cnt;
        while (cnt--) st.insert(-sg[i].e);
    }
    printf("%d", res);
    return 0;
}

13940번: Pohlepko

https://www.acmicpc.net/problem/13940

$O(n^2+m^2)$

길이 l짜리 단어들 중 사전순으로 가장 빠른 단어는 다른 단어들과 앞의 i(i<l)개의 문자를 가지고 사전순 비교를 해도 가장 빠르다.
따라서 앞에서부터 보며 사전순으로 가장 빠르지 않은 문자를 가진 단어들을 해집합에서 제거해 나감으로써 최종 답을 구할 수 있다.

이러한 성질에 따라 / 모양의 대각선을 위에서 아래로 훑으면서 걸치는 문자들에 대해 사전순 비교를 한다.
이 중 가장빠른 문자에 대해 아래 혹은 오른쪽의 문자를 붙여 문자열을 만들 수 있으니 이를 고려하여 해집합을 구성한다.

#include<cstdio>
int n, m, ck[2000][2000];
char s[2000][2001], r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    ck[0][0] = 1;
    r = s[0][0];
    for (int i = 0; i < n + m - 1; i++) {
        putchar(r);
        char t = 'z';
        for (int j = 0; j <= i; j++) {
            int x = i - j, y = j;
            if (x >= n || y >= m || !ck[x][y] || s[x][y] ^ r) continue;
            if (x + 1 < n&&t >= s[x + 1][y]) ck[x + 1][y] = 1, t = s[x + 1][y];
            if (y + 1 < m&&t >= s[x][y + 1]) ck[x][y + 1] = 1, t = s[x][y + 1];
        }
        r = t;
    }
    return 0;
}

13904번: 과제

https://www.acmicpc.net/problem/13904


$O(n\lg n)$

과제마감일 순으로 보면서 w1~wi 중 큰 순으로 최대 di개 이외 나머지는 스케줄 상에서 제외한다.

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n, res;
priority_queue<int> pq;
pair<int, int> p[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        pq.push(-p[i].second);
        res += p[i].second;
        if (pq.size() > p[i].first) res += pq.top(), pq.pop();
    }
    printf("%d", res);
    return 0;
}

2533번: 사회망 서비스(SNS)

https://www.acmicpc.net/problem/2533


$O(n)$

1번 정점이 root인 rooted tree를 만들어보자.
자식노드 중 얼리어 답터가 아닌 노드가 있으면 해당 노드는 얼리어 답터이어야 한다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e6;
int n, ck[MXN + 1], res;
vector<int> adj[MXN + 1];
void f(int h, int p) {
    int flag = 0;
    for (auto it : adj[h]) if (it^p) {
        f(it, h);
        flag |= !ck[it];
    }
    if (flag) ck[h] = 1, res++;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    printf("%d", res);
    return 0;
}

4003번: 경비병

https://www.acmicpc.net/problem/4003


$O(n+m\lg m)$

'i번째 덤불에 닌자가 확실히 있다.'
<->
'i번째 덤불에 닌자가 없다면 주어진 조건에 모순이 생긴다.'

따라서 i번째 덤불에 닌자가 없다고 가정한 뒤, 주어진 조건에 따라 k가 배치할 수 있는 닌자들 수의 최댓값과 최솟값 사이에 있는지 판별하면 된다.

배치 가능한 닌자들의 최댓값은 경비병이 닌자가 없다고 한 구간을 제외하고 나머지 덤불에 모두 배치한 닌자의 수이다. 당연하게도 k는 이 값보다 작거나 같으며 같은 경우에는 해당 덤불 모두에 닌자가 존재한다.

배치 가능한 닌자들의 최솟값은 그리디 알고리즘을 통해 구할 수 있다.
i번째 경비병의 정보를 통해 닌자가 존재할 수 있는 덤불 위치의 최솟값을 sli, 최댓값을 sri라 하자.
배치된 닌자들의 수가 최소가 될 때, 왼쪽으로부터 i번째인 닌자를 최대한 오른쪽으로 배치했을 때 위치 r[i]라 하자. 그러면 r[i]는 r[i-1]<slj인 정보들 중 srj의 최솟값이 된다. 비슷한 방법으로 왼쪽으로부터 i번째인 닌자를 최대한 왼쪽으로 배치했을 때 위치 l[i]를 구할 수 있고 배치된 닌자들의 최솟값도 구할 수 있다.

이 최솟값을 t라고 하자. 다음 두 경우가 존재한다.
i) t=k
l[i]=r[i]인 덤불에 닌자가 확실히 있다.
ii) t<k
sl[i]=sr[i]인 덤불에 닌자가 확실히 있다.
sl[i]<sr[i]일 때는 해당 덤불 구간 중 한 덤불에 닌자가 없다고 가정해도 나머지 덤불에 적절히 닌자를 배치하면 가능하기 때문이다. 이 때 추가될 닌자는 많아야 2명이다.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int MXN = 1e5;
int n, k, m, s[MXN + 2];
vector<pair<int, int> > sg;
vector<int> sl, sr, l, r, v, res;
int main() {
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (c) sg.push_back({ b,-a });
        else s[a]++, s[b + 1]--;
    }
    for (int i = 1; i <= n; i++) if (!(s[i] += s[i - 1])) v.push_back(i);
    sort(sg.begin(), sg.end());
    for (int i = 0, t = 0, lp = 0, rp = 0; i<sg.size(); i++) if (t > sg[i].second) {
        t = sg[i].second;
        for (; v[lp] < -t; lp++);
        for (; rp < v.size() && v[rp] <= sg[i].first; rp++);
        sl.push_back(v[lp]);
        sr.push_back(v[rp - 1]);
    }
    for (int i = 0, t = 0; i < sl.size(); i++) if (t < sl[i]) r.push_back(t = sr[i]);
    for (int i = sl.size(), t = n + 1; i--;) if (t > sr[i]) l.push_back(t = sl[i]);
    if (v.size() == k) res = v;
    else if (r.size() == k) {
        for (int i = 0; i < r.size(); i++) if (r[i] == l[r.size() - 1 - i]) res.push_back(r[i]);
    }
    else {
        for (int i = 0; i < sr.size(); i++) if (sl[i] == sr[i]) res.push_back(sr[i]);
    }
    if (res.empty()) puts("-1");
    else for (auto it : res) printf("%d\n", it);
    return 0;
}

2534번: 카드 배열

https://www.acmicpc.net/problem/2534


$O(n\lg n)$

#include<cstdio>
#include<queue>
#include<vector>
#define mod 1000000007
using namespace std;
const int MXN = 3e5;
int n, k, p, ind[2][MXN], r[2][MXN], s, od[MXN];
vector<int> adj[2][MXN];
priority_queue<int> pq;
void f(int t) {
    for (int i = 0; i < k; i++) if (!ind[t][i]) pq.push(-i);
    int i = 0;
    while (!pq.empty()) {
        int h = -pq.top();
        pq.pop();
        r[t][h] = od[i++];
        for (auto it : adj[t][h]) if (!--ind[t][it]) pq.push(-it);
    }
}
int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 0, x, y; i < p; i++) {
        scanf("%d%d", &x, &y);
        adj[0][x].push_back(y);
        adj[1][y].push_back(x);
        ind[0][y]++;
        ind[1][x]++;
    }
    for (int i = 0; i < k; i++) od[i] = k - 1 - i;
    f(0);
    for (int i = 0; i < k; i++) od[i] = n - k + i;
    f(1);
    for (int i = k; i--;) s = ((long long)s*n + r[1][i] - r[0][i] + mod) % mod;
    printf("%d", s);
    return 0;
}