2842번: POŠTAR

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

방문한 칸의 최소 높이가 x일 때 메일을 모두 보낼수 있는 방문한 칸의 최대 고도의 최솟값을 f(x)라 하자.
f(x)는 단조증가 함수가 된다. 고로 l=x, r=f(x)로 잡고 inchworm 알고리즘을 적용할 수 있다.
[l,r] 구간의 고도에 해당하는 칸만을 방문하여 모든 메일을 배달할 수 있다면 l++, 그렇지 않다면 r++을 해주며 모든 x에 대한 f(x) 값을 구한다. 답은 이러한 f(x) - x 들 중 최솟값이 된다.

시간복잡도는 $O(n^4)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int n, a[50][50], vis[50][50], sx, sy, res = 1e9, v[2500], l, r;
char s[50][51];
void f(int x, int y) {
    if (x < 0 || y < 0 || x == n || y == n || vis[x][y] || a[x][y]<v[l] || a[x][y]>v[r]) return;
    vis[x][y] = 1;
    for (int i = 0; i < 8; i++) f(x + dx[i], y + dy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j), v[i*n + j] = a[i][j];
    sort(v, v + n*n);
    while (r < n*n) {
        f(sx, sy);
        int flag = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && s[i][j] == 'K') flag = 1;
                vis[i][j] = 0;
            }
        }
        flag ? r++ : res = min(res, v[r] - v[l++]);
    }
    printf("%d", res);
    return 0;
}

13561번: House Rental

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

$O(n\lg n)$

두 개의 포인터를 사용하여 k 종류의 시설을 포함하는 최소 크기의 구간을 모두 탐색한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int k, n, cnt, ck[100001], mini = 2e9, res, l, r;
pair<int, int> p[1000000];
int main() {
    scanf("%d%d", &k, &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + n);
    while (r < n) {
        cnt += !ck[p[r++].second]++;
        while (cnt == k) {
            int t = p[r - 1].first - p[l].first + 1 >> 1;
            if (t < mini) mini = t, res = p[r - 1].first - t;
            cnt -= !--ck[p[l++].second];
        }
    }
    printf("%d", res);
    return 0;
}

2230번: 수 고르기

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


$O(n\lg n)$

two pointers를 사용한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[100000], r = 2e9;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    int i = 0, j = 0;
    while (j < n) {
        if (a[j] - a[i] < m) j++;
        else r = min(r, a[j] - a[i++]);
    }
    printf("%d", r);
    return 0;
}

3649번: Joint Venture

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


$O(n\lg n)$

먼저 l[i]를 정렬한다.
처음 i=0, j=n-1
i<j일 때까지
l[i]+l[j]<x이면 i++
l[i]+l[j]>x이면 j--
l[i]==l[j]이면 답을 출력한다.

l[i]==l[j]인 경우가 없다면 danger을 출력한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int x, n, l[1000000];
int main() {
    while (~scanf("%d", &x)) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", l + i);
        sort(l, l + n);
        int i = 0, j = n - 1;
        x *= 1e7;
        while (i < j) {
            if (l[i] + l[j] < x) i++;
            else if (l[i] + l[j] > x) j--;
            else {
                printf("yes %d %d\n", l[i], l[j]);
                break;
            }
        }
        if (i >= j) puts("danger");
    }
    return 0;
}

2415번: Rectangle

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


$O(n^2(C+\lg n))$

네 점이 직사각형을 이룰 필요충분조건은
마주보는 점을 연결하여 만든 두 선분의 길이와 그 절반에 위치한 중심이 일치하는 것이다.
이를 이용해 임의의 두 점에 대해 선분을 만들어 (길이, 중심점)이 같은 쌍끼리 모아서 최대 직사각형을 찾으면 된다.

주어진 점들 좌표가 정수이므로 중심점과 이로부터 거리(r)가 같은 점들은 그리 많지 않다.
(http://math.stackexchange.com/questions/17496/number-of-integer-solutions-of-x2-y2-k)
그래서 중심점, r이 같은 모든 선분쌍에 대해 직사각형을 만들어보며 최대 넓이를 찾아도 괜찮다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> point;
const int MXN = 1500;
int n, sz;
ll r;
point p[MXN];
pair<pair<point, ll>, point> a[MXN*MXN];
ll dis(point i, point j) {
    return (ll)(i.x - j.x)*(i.x - j.x) + (ll)(i.y - j.y)*(i.y - j.y);
}
ll ccw(point i, point j) {
    return (ll)i.x*j.y - (ll)i.y*j.x;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        for (int j = 0; j < i; j++) a[sz++] = { { { p[i].x + p[j].x,p[i].y + p[j].y },dis(p[i],p[j]) },{ p[i].x - p[j].x,p[i].y - p[j].y } };
    }
    sort(a, a + sz);
    for (int i = 0; i < sz; i++)
        for (int j = i; j < sz&&a[i].x == a[j].x; j++) r = max(r, abs(ccw(a[i].y, a[j].y)));
    printf("%lld", r / 2);
    return 0;
}

$O(n^2\lg n)$

(길이, 중심점)이 같은 선분들에 대해

중심점을 기준으로 끝점들을 시계방향 정렬한 뒤 넓이를 가지고 inchworm 알고리즘을 돌려도 된다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> point;
typedef pair<pair<point, ll>, point> tp;
const int MXN = 1500;
int n, sz;
ll r;
point p[MXN];
tp a[MXN*MXN];
ll dis(point i, point j) {
    return (ll)(i.x - j.x)*(i.x - j.x) + (ll)(i.y - j.y)*(i.y - j.y);
}
ll ccw(point i, point j) {
    return (ll)i.x*j.y - (ll)i.y*j.x;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        for (int j = 0; j < i; j++) {
            int dx = p[i].x - p[j].x, dy = p[i].y - p[j].y;
            if (dx < 0) dx *= -1, dy *= -1;
            a[sz++] = { { { p[i].x + p[j].x,p[i].y + p[j].y },dis(p[i],p[j]) },{ dx,dy } };
        }
    }
    sort(a, a + sz, [](tp i, tp j) {return i.x < j.x || i.x == j.x&&ccw(i.y, j.y)>0; });
    for (int i = 0, j; i < sz; i++) {
        if (!i || a[i - 1].x != a[i].x) j = i;
        while (j + 1 < sz&&a[i].x == a[j + 1].x&&ccw(a[i].y, a[j].y) < ccw(a[i].y, a[j + 1].y)) j++;
        r = max(r, ccw(a[i].y, a[j].y));
    }
    printf("%lld", r / 2);
    return 0;
}

1806번: 부분합

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


$O(n)$

j<i tot=a[j+1]+a[j+2]+...+a[i]
i를 증가시키며 tot>s이면 tot<=s일 때까지 j를 증가시킨다.
tot>s일 때 i-j의 최솟값을 구한다.

#include<cstdio>
int n, s, a[100001], r = 1e9;
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1, j = 0; i <= n; i++) {
        scanf("%d", a + i);
        a[i] += a[i - 1];
        for (; a[i] - a[j] > s; j++) if (r > i - j) r = i - j;
    }
    printf("%d", a[n] > s ? r : 0);
    return 0;
}

2003번: 수들의 합 2

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


$O(n)$

inchworm algorithm을 이용한다.

#include<cstdio>
int n, m, r, h, a[10000], s;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        s += a[i];
        while (s > m) s -= a[h++];
        r += s == m;
    }
    printf("%d", r);
    return 0;
}

12005번: Diamond Collector (Bronze)

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


$O(n\lg n)$

정렬한 다음, 차가 k이하가 되는 최대 구간 크기를 구한다.

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