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

3033번: DVAPUT

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

Rabin-Karp 알고리즘으로 $O(l)$에 길이가 x인 같은 문자열이 두 번 나오는지 확인할 수 있다.
x에 대해 파라메트릭 서치를 한다.

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

#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
const long long mod = (1LL << 55) - 55;
int l;
char s[200001];
int main() {
    scanf("%d%s", &l, s);
    int low = 1, up = l, mid;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_set<long long> st;
        long long p = mod - 1, t = 0;
        int i = 0;
        for (; i < mid; i++) t = (t * 127 + s[i]) % mod, p = p * 127 % mod;
        for (; i <= l; i++) {
            if (st.find(t) != st.end()) break;
            st.insert(t);
            t = (t * 127 + p*s[i - mid] + s[i]) % mod;
        }
        i > l ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", up);
    return 0;
}

답은 lcp 길이의 최댓값이다.

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

#include<cstdio>
#include<algorithm>
using namespace std;
int l, c[200000], a[200000], b[200000], sa[200000], sz, r;
char s[200001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < l; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = l; i--;) sa[--c[a[b[i]]]] = b[i];
}
int main() {
    scanf("%d%s", &l, s);
    sz = max(l, 128);
    for (int i = 0; i < l; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= l; i <<= 1) {
        k = 0;
        for (int j = l - i; j < l; j++) b[k++] = j;
        for (int j = 0; j < l; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < l; j++) b[sa[j]] = !j || sa[j - 1] + i < l && sa[j] + i < l && a[sa[j - 1]] == a[sa[j]] && a[sa[j - 1] + i] == a[sa[j] + i] ? k : ++k;
        for (int j = 0; j < l; j++) a[j] = b[j];
    }
    for (int i = 0, j = 0; i < l; r = max(r, j ? j-- : 0), i++)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
    printf("%d", r);
    return 0;
}

4223번: Mummy Madness

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


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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e6;
struct st {
    int x, l, r, c;
}line[200000];
int n, x[100000], y[100000], len[MX * 8], cnt[MX * 8];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) cnt[h] += x;
    else update(h * 2 + 1, l, (l + r) / 2, gl, gr, x), update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    len[h] = cnt[h] ? r - l + 1 : l^r ? len[h * 2 + 1] + len[h * 2 + 2] : 0;
}
bool f(int t) {
    int sz = 0;
    for (int i = 0; i < n; i++) {
        int sx = max(x[i] - t, MX - t), ex = min(x[i] + t, MX + t),
            sy = max(y[i] - t, MX - t), ey = min(y[i] + t, MX + t);
        if (sx > ex || sy > ey) continue;
        line[sz++] = { sx,sy,ey,1 };
        line[sz++] = { ex + 1,sy,ey,-1 };
    }
    sort(line, line + sz, [](st i, st j) {return i.x < j.x; });
    long long area = 0;
    for (int i = 0; i < sz; i++) {
        if (i) area += 1LL * len[0] * (line[i].x - line[i - 1].x);
        update(0, 0, MX * 2 + 1, line[i].l, line[i].r, line[i].c);
    }
    return area < 4LL * t*t + 4 * t + 1;
}
int main() {
    for (int t = 1; scanf("%d", &n), ~n; t++) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            x[i] += MX;
            y[i] += MX;
        }
        int low = 0, up = MX, mid;
        while (low <= up) {
            mid = (low + up) / 2;
            f(mid) ? low = mid + 1 : up = mid - 1;
        }
        printf("Case %d: ", t);
        low > MX ? puts("never") : printf("%d\n", low);
    }
    return 0;
}

14452번: Cow Dance Show

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


$O(n\lg^2n)$

최소 t는 n에 대한 단조 감소 함수이므로 t<=t_max를 만족하는지 묻는 결정문제로 바꿔 풀 수 있다. 현재 댄스가 가장 빨리 끝나는 소를 pop하고 새로운 소를 추가하며 우선순위 큐를 관리하면 해당 n에 대한 최소 t를 구할 수 있다.

#include<cstdio>
#include<queue>
using namespace std;
int t, n, a[100000];
bool f(int x) {
    priority_queue<int> pq;
    for (int i = 0; i < x; i++) pq.push(-a[i]);
    for (int i = x; i < n; i++) {
        pq.push(pq.top() - a[i]);
        pq.pop();
    }
    while (pq.size() - 1) pq.pop();
    return -pq.top() <= t;
}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int low = 1, high = n, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        f(mid) ? high = mid - 1 : low = mid + 1;
    }
    printf("%d", low);
    return 0;
}

2126번: 지진

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


$O(cm\lg m)$

시간당 최대 이득이 x이상인가를 확인하는 결정 문제로 바꿔보자.
mst를 이루는 간선들의 (ci,ti)에 대해
{f-sum(ci)}/sum(ti) >= x
정리하면 f>=sum(ci+ti*x)
우변은 잘 알려진 프림, 크루스칼 알고리즘을 통해 최솟값을 구할 수 있다.

이제 파라메트릭 서치를 할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 400, MXM = 1e4;
struct st {
    int u, v, c, t;
}e[MXM];
int n, m, f, p[MXN + 1];
double low, up, mid;
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
bool mst() {
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(e, e + m, [](st i, st j) {return i.c + i.t*mid < j.c + j.t*mid; });
    double s = 0;
    for (int i = 0; i < m; i++) if (par(e[i].u) ^ par(e[i].v)) {
        p[par(e[i].u)] = par(e[i].v);
        s += e[i].c + e[i].t*mid;
    }
    return s <= f;
}
int main() {
    scanf("%d%d%d", &n, &m, &f);
    for (int i = 0; i < m; i++) scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].c, &e[i].t);
    up = f;
    for (int i = 0; i < 100; i++) {
        mid = (low + up) / 2;
        mst() ? low = mid : up = mid;
    }
    printf("%.4lf", mid);
    return 0;
}

3487번: Copying Books

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

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_N = 500;
typedef long long ll;
int t, n, k, a[MAX_N];
vector<int> r;
bool f(ll x) {
    vector<int> t;
    ll c = 1, s = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i]>x) return false;
        if (s + a[i]>x || i + 1 == k - c) s = a[i], c++, t.push_back(i);
        else s += a[i];
    }
    if (c == k) {
        r = t;
        return true;
    }
    return false;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        int i;
        for (i = 0; i<n; i++) scanf("%d", a + i);
        ll h = 0, t = 5e9, m;
        while (h <= t) {
            m = (h + t) / 2;
            if (f(m)) t = m - 1;
            else h = m + 1;
        }
        i = 0;
        for (int j = r.size() - 1; j >= 0; j--) {
            for (; i <= r[j]; i++) printf("%d ", a[i]);
            printf("/ ");
        }
        for (; i<n; i++) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}

8875번: 장난감 정리 로봇

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

$O((a+b+t\lg t)\lg t)$

먼저 1분째 정리가 가능한지 확인하는 그리디 풀이법에 대해 알아보자.

1. X[1...a]를 오름차순 정렬한다.
2. i를 증가시켜가며 무게가 X[i]이하인 장난감들 중 최대 크기인 장난감을 제외한다.
3. 임의의 i에 대해 Y[i]이하인 장난감들 중 최대 크기인 장난감을 제외한다.
4. 남은 장난감이 있다면 불가능, 아니면 가능하다.

c분 이하에 정리가 가능한지 확인하기 위해선 각 로봇들이 c개 있다고 가정하고 위 알고리즘을 적용하면 된다.
즉, 결정문제로 바꿔서 파라메트릭 서치를 이용하면 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int a, b, t, x[50000], y[50000];
pair<int, int> p[1000000];
bool f(int c) {
    priority_queue<int> pq;
    int j = 0;
    for (int i = 0; i < a; i++) {
        while (j < t&&p[j].first < x[i]) pq.push(p[j++].second);
        for (int k = c; k--&&!pq.empty();) pq.pop();
    }
    for (; j < t; j++) pq.push(p[j].second);
    for (int i = b; i--&&!pq.empty();) {
        if (pq.top() >= y[i]) return false;
        for (int k = c; k--&&!pq.empty();) pq.pop();
    }
    return pq.empty();
}
int main() {
    scanf("%d%d%d", &a, &b, &t);
    for (int i = 0; i < a; i++) scanf("%d", x + i);
    for (int i = 0; i < b; i++) scanf("%d", y + i);
    for (int i = 0; i < t; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(x, x + a);
    sort(y, y + b);
    sort(p, p + t);
    int low = 1, up = t, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        f(mid) ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", low > t ? -1 : low);
    return 0;
}

10019번: Sabotage

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


$O(nC)$

s[i]: m[1...i]의 합

파라매트릭 서치를 하기 위해 문제를 평균이 p이하가 될 수 있는지 결정하는 문제로 바꿔보자.
즉,
(s[n]-s[i]+s[j])/(n-i+j)<=p (1<=j<i<n) 인 i, j가 존재하는지 확인하면 된다.
위 식은
s[n]-p*n+(p*i-s[i])-(p*j-s[j])<=0 과 동치이고
이는 f(x)=p*x-s[x]을 최댓값으로 만드는 x=j를 기억하면 매 i마다 s[n]-p*n+f(i)-f(j)의 최솟값을 O(1)에 찾을 수 있어서
매번 O(n)에 평균을 p이하로 만들 수 있는지 확인이 가능하다.

#include<cstdio>
const int MXN = 1e5;
int n, s[MXN + 1];
bool f(double a) {
    double maxi = a - s[1];
    for (int i = 2; i < n; i++) {
        if (s[n] - a*n + a*i - s[i] - maxi <= 0) return 1;
        if (a*i - s[i]>maxi) maxi = a*i - s[i];
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
    double low = 1, up = 1e4, mid;
    while (up - low > 1e-6) {
        mid = (low + up) / 2;
        f(mid) ? up = mid : low = mid;
    }
    printf("%.3lf", mid);
    return 0;
}

2022번: 사다리

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


$O(t\lg L)$ // L: 탐색구간 크기

떨어진 거리 d라 할 때 f(d)를 교점의 높이라 하자.
왼쪽 빌딩 교점의 높이: a
오른쪽 빌딩 교점의 높이: b
a=sqrt(x*x-d*d)
b=sqrt(y*y-d*d)
f(d)=a*b/(a+b)
y=f(x)는 감소함수 이므로 파라매트릭 서치를 통해 본 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
double x, y, c;
int main() {
    while (~scanf("%lf%lf%lf", &x, &y, &c)) {
        double low = 0, up = min(x, y), m;
        for (int i = 0; i < 100; i++) {
            m = (low + up) / 2;
            1 / c < 1 / sqrt(x*x - m*m) + 1 / sqrt(y*y - m*m) ? up = m : low = m;
        }
        printf("%.3lf\n", m);
    }
    return 0;
}

1561번: 놀이 공원

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


$O(mlgL)$ // L: 탐색 구간 크기

t=0, 1, ... 증가하면서
t%a[i]==0인 i번 놀이 기구를 탄다고 하자.

f(x)를 t=x일 때까지 놀이 기구를 탄 횟수라고 하자.
즉, f(x)=sum(x/s[i])

그러면 n번 아이가 t=a에 놀이 기구를 탔다면
x>=a인 모든 x에 대해 f(x)>=n이고,
x<a인 모든 x에 대해 f(x)<n일 것이다.

이제 파라매트릭 서치를 할 수 있다.

#include<cstdio>
typedef long long ll;
int n, m, a[10000];
ll f(ll x) {
    ll s = 0;
    for (int i = 0; i < m; i++) s += x / a[i];
    return s;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d", a + i);
    ll low = 1, up = 6e10, mid;
    n -= m;
    while (low <= up) {
        mid = (low + up) / 2;
        f(mid) >= n ? up = mid - 1 : low = mid + 1;
    }
    int c = f(low) - n;
    for (int i = m; i--;) if (low%a[i] == 0 && !c--) {
        printf("%d", i + 1);
        break;
    }
    return 0;
}

1902번: 램프

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


$O(nC)$ // C는 삼분 검색에서 함수의 최대 호출 수

주어진 선분을 연장한 직선을 그리고 이들 중 최댓값만 취해보자. 그러면 아래로 볼록한 껍질이 그려진다.
삼분검색을 하자.

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double x[5000], y[5000], r;
double f(double t) {
        double rt = 0;
        for (int i = 1; i < n; i++)
            rt = max(rt, (y[i] - y[i - 1]) / (x[i] - x[i - 1])*(t - x[i]) + y[i]);
        return rt;
}
int main() {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%lf%lf", x + i, y + i);
        double low = x[0], up = x[n - 1], m1, m2;
        while (up - low>1e-9) {
                m1 = (low * 2 + up) / 3;
                m2 = (low + up * 2) / 3;
                f(m1) < f(m2) ? up = m2 : low = m1;
        }
        printf("%.2lf", f(m1));
        return 0;
}

2343번: 기타 레슨

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


$O(n\lg t)$

블루레이의 길이를 기준으로 파라매트릭 서치를 한다.

#include<cstdio>
int n, m, a[100000], low, up = 1e9, mid;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        if (a[i] > low) low = a[i];
    }
    while (low <= up) {
        mid = (low + up) / 2;
        int s = 0, c = 1;
        for (int i = 0; i < n; i++) {
            if (s + a[i] > mid) s = 0, c++;
            s += a[i];
        }
        c > m ? low = mid + 1 : up = mid - 1;
    }
    printf("%d", low);
    return 0;
}

2110번: 공유기 설치

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


$O(n\lg x)$

공유기간 간격을 기준으로 파라매트릭 서치를 한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, c, a[200000];
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    int low = 1, up = 1e9, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        int cnt = 1, t = a[0];
        for (int i = 1; i < n; i++) if (a[i] - t >= mid) t = a[i], cnt++;
        cnt < c ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", up);
    return 0;
}

2805번: 나무 자르기

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


$O(n\lg h)$

자르는 높이를 기준으로 파라매트릭 서치를 한다.

#include<cstdio>
int n, m, a[1000000];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int l = 0, r = 1e9, c;
    while (l <= r) {
        c = (l + r) / 2;
        long long s = 0;
        for (int i = 0; i < n; i++) if (a[i] > c) s += a[i] - c;
        s < m ? r = c - 1 : l = c + 1;
    }
    printf("%d", r);
    return 0;
}

13397번: 구간 나누기 2

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


$O(n\lg c)$

차이를 기준으로 파라매트릭 서치를 한다.
최대 차이 x가 가능한지 판단하기 위해 주어진 배열 {ai}를 앞에서부터 x가 넘는 시점마다 구간을 나눈다.
나눈 구간 개수가 m이하면 가능하다.

#include<cstdio>
int n, m, a[5000];
int f(int x) {
    int mini = a[0], maxi = a[0], res = 1;
    for (int i = 1; i<n; i++) {
        if (a[i]<mini) mini = a[i];
        if (a[i]>maxi) maxi = a[i];
        if (maxi - mini>x) mini = maxi = a[i], res++;
    }
    return res;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    int l = 0, r = 9999, c;
    while (l <= r) {
        c = (l + r) / 2;
        f(c)>m ? l = c + 1 : r = c - 1;
    }
    printf("%d", l);
    return 0;
}

1654번: 랜선 자르기

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


$O(n\lg l)$

랜선의 길이를 기준으로 파라매트릭 서치를 한다.

#include<cstdio>
int n, k, a[1000000];
long long l = 1, r = 0x7fffffff, m;
int f(int x) {
    int s = 0;
    for (int i = 0; i < n; i++) s += a[i] / x;
    return s;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    while (l <= r) {
        m = (l + r) / 2;
        f(m) < k ? r = m - 1 : l = m + 1;
    }
    printf("%lld", r);
    return 0;
}

1508번: 레이스

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


$O(k\lg n)$

파라매트릭 서치를 이용한다.

#include<cstdio>
int n, m, k, a[50], c, t;
bool f(int x) {
    t = -n;
    for (int i = c = 0; i < k; i++) if (a[i] - t >= x) t = a[i], c++;
    return c >= m;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++) scanf("%d", a + i);
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        f(mid) ? l = mid + 1 : r = mid - 1;
    }
    t = -n;
    for (int i = c = 0; i < k; i++) {
        printf("%d", a[i] - t >= r&&c < m);
        if (a[i] - t >= r) t = a[i], c++;
    }
    return 0;
}

1300번: K번째 수

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


$O(n\lg k)$

파라매트릭 서치를 이용한다.

#include<cstdio>
#define min(x,y) x<y?x:y;
int n, k, l, r, m;
int main() {
    scanf("%d%d", &n, &k);
    l = 1; r = k;
    while (l <= r) {
        long long c = 0;
        m = (l + r) / 2;
        for (int i = 1; i <= n; i++) c += min(n, m / i);
        c < k ? l = m + 1 : r = m - 1;
    }
    printf("%d", l);
    return 0;
}

2792번: 보석 상자

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


$O(m\lg a)$

질투심을 가지고 파라매트릭 서치를 해본다.

#include<cstdio>
int n, m, a[300000];
int f(int x) {
    int s = 0;
    for (int i = 0; i < m; i++) s += (a[i] - 1) / x + 1;
    return s;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d", a + i);
    int l = 1, r = 1e9, c;
    while (l <= r) {
        c = (l + r) / 2;
        if (f(c) <= n) r = c - 1;
        else l = c + 1;
    }
    printf("%d", l);
    return 0;
}