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

11503번: Tree Edit

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

T1, T2의 각 노드에 서로 다른 번호가 부여되어 있다고 하자.
i번 노드의 자식들을 ci_1, ci_2, ...라고 하자.
ed[i][j]: i번 노드가 루트인 T1의 서브트리를 j번 노드가 루트인 T2의 서브트리로 바꾸는데 필요한 최소 편집 연산 수
ed[i][j]는 ed[ci_1..n][cj_1..m]들을 가지고 DP로 구할 수 있다.

dp[u][v]: ci_1..u 를 cj_1..v로 바꾸는데 필요한 최소 편집 연산 수
dp[u][v] = min(
dp[u-1][v] + (ci_u가 루트인 서브트리의 사이즈),
dp[u][v-1] + (cj_v가 루트인 서브트리의 사이즈),
dp[u-1][v-1] + ed[ci_u][cj_v])
그러면 ed[i][j]는 dp[n][m]이 된다.

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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int tc, ed[2000][2000], sz[2000], pos, id;
char la[2000], s[3001];
vector<int> adj[2000];
int f(int l, int r) {
    if (~ed[l][r]) return ed[l][r];
    int n = adj[l].size(), m = adj[r].size();
    vector<vector<int> > dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + sz[adj[l][i - 1]];
    for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + sz[adj[r][i - 1]];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        dp[i][j] = min({ dp[i][j - 1] + sz[adj[r][j - 1]],
            dp[i - 1][j] + sz[adj[l][i - 1]],
            dp[i - 1][j - 1] + f(adj[l][i - 1], adj[r][j - 1]) });
    return ed[l][r] = dp[n][m] + (la[l] != la[r]);
}
void gen() {
    int h = id++, st = pos;
    adj[h].clear();
    la[h] = s[++pos];
    while (s[++pos] != ')') adj[h].push_back(id), gen();
    sz[h] = (pos - st) / 3 + 1;
}
void solve() {
    fill(&ed[0][0], &ed[1999][2000], -1);
    scanf("%s", s); id = pos = 0; gen();
    int t = id;
    scanf("%s", s); pos = 0; gen();
    printf("%d\n", f(0, t));
}
int main() {
    for (scanf("%d", &tc); tc--;) solve();
    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;
}

13282번: Bamboo Blossoms

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

i 보다 작으면서 가장 큰 i의 약수를 pi라고 하자.
그러면 i = m부터 보면서 pi<m인 i에 대해 i-year-bamboos를 심는게 최선이다.

시간복잡도는 $O(L(t+\lg L))$

#include<cstdio>
int m, n, p[8000001];
int main() {
    for (int i = 1; i <= 8e6; i++) for (int j = i * 2; j <= 8e6; j += i) p[j] = i;
    while (scanf("%d%d", &m, &n), m) {
        for (int i = m;; i++) if (!~(n -= p[i] < m)) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

13503번: 최소 체인 커버

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

최대 이분 매칭을 구해서 풀 수 있다.

모든 정점 i에 대해 source, sink와 각각 연결된 두 개의 정점 i, i'를 만들고
주어지는 간선 u -> v 마다 만들고 있는 이분 그래프에서 간선 u -> v' 을 추가한다.
이 그래프에서의 매칭을 원래 그래프에서 체인에 속한 간선들과 대응시킬 수 있다.
(체인 수) = n - (체인에 속한 간선 수) 이므로 (최소 체인 수) = n - (최대 매칭 수) 이다.

시간복잡도는 $O(nm)$

#include<cstdio>
#include<vector>
using namespace std;
int n, m, vis[10001], rev[10001], t, res;
vector<int> adj[10001];
int f(int h) {
    vis[h] = t;
    for (auto it : adj[h]) if (!rev[it] || vis[rev[it]] ^ t && f(rev[it])) {
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
    }
    res = n;
    for (t = 1; t <= n; t++) res -= f(t);
    printf("%d", res);
    return 0;
}

7332번: Cashier Employment

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

각 시간대마다 필요한 알바 수와 8시간동안 연속적으로 고용할 수 있는 알바 정보가 주어졌을 때 필요한 알바 수의 최솟값을 구하는 문제이다.

r[i]: i-1 ~ i시에 필요한 알바 수
t[i]: i-1 ~ i+7시에 쓸 수 있는 알바 수
* 굳이 i-1로 한 이유는 후에 prefix sum을 사용하는데 있어 -1번째 인덱스가 나오지 않게 하기 위함이다.

그러면 문제는 0<= a[i] <= t[i]인 a[i]를 잘 골라
i<8 일 때, a[17+i] + ... + a[24] + a[1] + ... + a[i] >= r[i]
i>=8 일 때, a[i-7] + a[i-6] + ... + a[i] >= r[i]
를 만족하는 sum(a[i])의 최솟값을 구하는 문제라고 할 수 있다.

s[i] = sum(a[j]: 1<=j<=i)로 놓고 모든 조건을 일차선형부등식 꼴로 만들어 보면
0 <= s[i] - s[i-1] <= t[i]
i<8 일 때, s[24] - s[16+i] + s[i] >= r[i]
i>=8 일 때, s[i] - s[i-8] >= r[i]

이제 상수 lmt <= s[24]로 놓으면

s[24] - lmt >= s[0]

s[i] >= s[i-1]

s[i-1] + t[i] >= s[i]

i<8 일 때, s[i] + lmt - r[i] >= s[16+i]
i>=8 일 때, s[i] - r[i] >= s[i-8]

모든 부등식이 x + w >= y 꼴의 형태이므로 각 조건에 대응되는 가중치가 w인 x -> y 간선들을 추가한 뒤, 최단거리 알고리즘을 이용해 주어진 부등식들이 가능한지 판단할 수 있다.
부등식들이 모두 성립하는 최소 0 <= lmt <= n를 찾는다. 불가능하면 No Solution을 출력한다.

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

#include<cstdio>
#include<algorithm>
using namespace std;
int tc, n, t[25], r[25], dp[25][25];
bool f(int lmt) {
    fill(dp[0], dp[25], 1e9);
    for (int i = 0; i < 25; i++) {
        dp[i][i] = 0;
        if (i) dp[i - 1][i] = t[i], dp[i][i - 1] = 0;
    }
    int i = 1;
    for (; i < 8; i++) dp[i][i + 16] = lmt - r[i];
    for (; i < 25; i++) dp[i][i - 8] = -r[i];
    dp[24][0] = -lmt;
    for (int i = 0; i < 25; i++) for (int j = 0; j < 25; j++) for (int k = 0; k < 25; k++) dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]);
    for (int i = 0; i < 25; i++) if (dp[i][i] < 0) return false;
    return true;
}
void task() {
    for (int i = 1; i <= 24; i++) scanf("%d", r + i), t[i] = 0;
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) scanf("%d", &x), t[x + 1]++;
    for (int i = 0; i <= n; i++) if (f(i)) { printf("%d\n", i); return; }
    puts("No Solution");
}
int main() {
    for (scanf("%d", &tc); tc--;) task();
    return 0;
}

12736번: Fireworks

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

i번 연결점에 이어진 폭약들을 시각 t에 동시에 떠뜨리기 위한 최소 비용을 f_i(t)라고 하자. 이 함수는 t에 관한 아래로 볼록인 함수이다.
또한 이 함수는 i번 연결점 바로 다음에 이어진 a0, a1, ..., aj 번 연결점에 관한 최소 비용 함수로부터 구할 수 있다.
(그리 어렵지 않으니 함수가 어떻게 구해지는지 한 번 생각보자.)

이 과정에서 함수끼리의 덧셈 및 볼록껍질의 제약적인 수정이 요구된다.
볼록 함수 끼리의 연산을 효율적으로 하기 위해 볼록 함수를 y절편, 기울기가 1씩 증가하는 t를 우선순위 큐에 저장해놓는다.
- 두 함수를 더하기 위해서는 y절편끼리 더하고 사이즈가 큰 우선순위 큐에 작은 우선순위 큐의 원소들을 모두 빼서 넣어주면 된다. ... (*)
- 볼록 껍질에서 기울기가 1보다 큰 부분을 없애야 하는 경우가 있다. 이 경우엔 간단히 우선순위 큐에서 pop 해주면 된다.
- 볼록 껍질에서 기울기가 -1인 부분을 늘려야 하는 경우가 있다. 이 경우엔 y절편과 기울기가 0인 부분을 잘 수정해주면 된다.

(*) 부분의 시간복잡도를 계산해보자.
먼저, 각 f_i(t)를 이루는 점의 수(곧, 우선순위 큐의 원소 개수)는 i번 연결점에 연결된 폭약의 수에 비례한다. 우선순위 큐 내부의 폭약에 관한 원소들은 (*) 부분에서 이동이 발생하고 그 때마다 자신이 속한 우선순위 큐의 사이즈가 2배이상으로 증가한다. 따라서 각 원소마다 이동횟수가 $O(\lg n)$로 제한되고 이동시 $O(\lg n)$의 시간이 걸리므로 총 시간복잡도는 $O(n\lg^2 n)$.

최종 시간복잡도는 $O(n\lg^2 n)$

#include<cstdio>
#include<queue>
using namespace std;
int n, m, p[300001], c[300001], sz[300001];
long long s[300001], l, r;
priority_queue<long long> *pq[300001];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++) scanf("%d%d", p + i, c + i);
    for (int i = n + 1; i <= n + m; i++) pq[i] = new priority_queue<long long>(2, 0);
    for (int i = n + m; i; i--) {
        while (sz[i]--) pq[i]->pop();
        r = pq[i]->top(); pq[i]->pop();
        l = pq[i]->top(); pq[i]->pop();
        pq[i]->push(l + c[i]);
        pq[i]->push(r + c[i]);
        s[p[i]] += s[i] + c[i];
        if (!pq[p[i]]) { pq[p[i]] = pq[i]; continue; }
        if (pq[p[i]]->size() < pq[i]->size()) swap(pq[p[i]], pq[i]);
        while (!pq[i]->empty()) pq[p[i]]->push(pq[i]->top()), pq[i]->pop();
        sz[p[i]]++;
    }
    pq[0]->pop();
    while (!pq[0]->empty()) s[0] -= pq[0]->top(), pq[0]->pop();
    printf("%lld", s[0]);
    return 0;
}

11069번: Particle

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

d = gcd(a, b)
(a', b') = (a / d, b / d)

주어진 직사각형을 각 변에 대한 거울상과 무한히 연결하고 이 필드 상에서 입자가 직선 운동을 한다고 생각할 수 있다.
문제의 규칙 하에 입자가 (x0, y0)에서 (x1, y1)로 속도(a', b')로 간다면 걸리는 최소 시간 tm은 다음 식을 만족하는 t(>0)중 최솟값이다.

i) x0 + a't = x1 + 2w*u  and  y0 + b't = y1 + 2h*v
ii) x0 + a't = -x1 + 2w*u  and  y0 + b't = y1 + 2h*v
iii) x0 + a't = x1 + 2w*u  and  y0 + b't = -y1 + 2h*v
iv) x0 + a't = -x1 + 2w*u and  y0 + b't = -y1 + 2h*v

이 중 (i)에 대해서만 풀어보자.
두 식은 모두 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
첫 번째 식의 t = p1 * x + q1,
두 번째 식의 t = p2 * y + q2 라 하자.
두 t는 같아야 하므로 p1 * x + q1 = p2 * y + q2
이를 만족하는 x 역시 Extended Euclidean 알고리즘으로 일반해를 구할 수 있다.
x = p3 * x' + q3라 하면
t = p1 * x + q1 = p1*p3*x' + q1*p3 + q3
이제 위 식을 만족하면서 0보다 큰 최소 t를 구할 수 있다.

마찬가지 방법으로 (i)~(iv)에 대해 구한 t 중 최솟값 tm을 구할 수 있다.
(x2, y2)에 가는데 걸리는 최소 시간 또한 같은 방법으로 구해서 걸린 시간을 비교한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, w, h, a0, b0, a1, b1, a2, b2, a, b;
int ee(int c1, int c2, int &r1, int &r2) {
    if (!c2) {
        r1 = 1; r2 = 0;
        return c1;
    }
    int ret = ee(c2, c1%c2, r2, r1);
    r2 -= c1 / c2*r1;
    return ret;
}
bool eq(int c1, int c2, int c3, int &r1, int &r2) {
    int u, v, ret = ee(c1, c2, u, v);
    if (c3%ret) return false;
    r1 = c2 / ret;
    r2 = 1LL * c3 / ret * u%r1;
    return true;
}
long long solve(int c1, int c2) {
    int p1, q1, p2, q2, p3, q3;
    if (!eq(a, -2 * w, c1 - a0, p1, q1) ||
        !eq(b, -2 * h, c2 - b0, p2, q2) ||
        !eq(p1, -p2, q2 - q1, p3, q3)) return 1e15;
    long long p4 = abs(1LL * p1*p3), q4 = 1LL * p1*q3 + q1;
    return (q4%p4 + p4) % p4;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d%d%d%d%d%d%d", &w, &h, &a0, &b0, &a1, &b1, &a2, &b2, &a, &b);
        int u, v, d = abs(ee(a, b, u, v));
        a /= d; b /= d;
        long long ret1 = min({ solve(a1, b1), solve(-a1, b1), solve(a1, -b1), solve(-a1, -b1) }),
            ret2 = min({ solve(a2, b2), solve(-a2, b2), solve(a2, -b2), solve(-a2, -b2) });
        puts(ret1^ret2 ? ret1 < ret2 ? "A" : "B" : "O");
    }
    return 0;
}

13326번: Diameter

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

주어진 점들 중 가장 먼 두 점을 s, e라고 하자. 답이 이 두 점 사이 거리보다 작기 위해선 s와 e가 서로 다른 그룹에 있어야 한다. 각 두 점이 속한 그룹을 S, E라 하자.

s와 e가 각각 중심이 되는 두 원(A, B)을 생각해보자. 이 두 원은 주어진 점들을 모두 포함하고, 각 원주에는 적어도 하나의 점이 존재한다.
이제 각 점들은 두 원과의 포함관계에 따라 다음과 같이 두 그룹으로 나눠질 수 있다.

i) A 안에 존재하고 B 안에 존재하지 않는 경우
S에 포함
ii) B 안에 존재하고 A 안에 존재하지 않는 경우
E에 포함
iii) A, B 안에 존재하는 경우
S 혹은 E 둘 중 아무 그룹에 포함

그런데 A, B가 만나는 경우 답은 A, B 반지름 합 이상이 되며, 이 값은 s와 e 사이 거리 이상이다. 따라서 두 원은 무조건 분리되도록 그려야 한다.

p[i]를 s로 부터 i번째 가까운 점이라고 하자. p[0...j], p[j+1...n-1] 두 그룹으로 나누어 원을 그려보면 j를 조절함에 따라 가능한 분리된 두 원을 모두 그려볼 수 있다.
답은 min( (p[0...j]에서 가장 먼 두 점 거리) + (p[j+1...n-1]에서 가장 먼 두 점 거리) )이 된다.

최종 시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
#define dis(u,v) ((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]))
int n, pfx, sfx[5000], a[5000], s, e, x[5000], y[5000];
double res = 1e9;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), a[i] = i;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dis(s, e) < dis(i, j)) s = i, e = j;
    sort(a, a + n, [](int u, int v) {return dis(s, u) < dis(s, v); });
    for (int i = n - 1; i--;) {
        sfx[i] = sfx[i + 1];
        for (int j = n; --j > i;) sfx[i] = max(sfx[i], dis(a[i], a[j]));
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) pfx = max(pfx, dis(a[i - 1], a[j]));
        res = min(res, sqrt(pfx) + sqrt(sfx[i]));
    }
    printf("%lf", res);
    return 0;
}

13330번: Palindromic

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

동적계획법을 이용해 해결할 수 있다.

s[i]: i번째 문자
lp[i][j]: s[j-i+1 ... j-i+1+k]와 s[j ... j-k]가 같은 최대 k
dp[i]: s[1...i]을 θ-팰린드롬 문자열들을 연결하여 만들 때 필요한 최소 문자열 수
자세한 구현은 다음 소스를 참고하자.


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

#include<cstdio>
#include<algorithm>
using namespace std;
int lp[10001][10001], n, k, l, dp[10001];
char s[10002];
int main() {
    scanf("%d%d%d%s", &n, &k, &l, s + 1);
    for (int i = 2; i <= n; i++) for (int j = i; j <= n; j++) if (s[j - i + 1] == s[j]) lp[i][j] = lp[i - 2][j - 1] + 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = n;
        for (int j = 2; j <= i; j++) if (2 * lp[j][i] * l >= j*k) dp[i] = min(dp[i], dp[i - j] + 1);
    }
    printf("%d", dp[n] < n ? dp[n] : 0);
    return 0;
}

13328번: Message Passing

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

dp[i]: 시각이 i일 때 전화 수
i) i < 0
dp[i] = 0
ii) i = 0
dp[i] = 1
iii) i > 0
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-d]

답은 dp[t]이다. 행렬을 이용하면 $O(\lg t)$ 횟수의 행렬 곱으로 답을 구할 수 있다.

#include<cstdio>
#define mod 31991
int d, t;
struct st {
    int m[50][50] = {};
    st operator*(st a) const {
        st ret;
        for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) {
            for (int k = 0; k < d; k++) ret.m[i][j] = (ret.m[i][j] + m[i][k] * a.m[k][j]) % mod;
        }
        return ret;
    }
}u, r;
int main() {
    scanf("%d%d", &d, &t);
    for (int i = 0; i < d; i++) r.m[i][i] = u.m[0][i] = 1;
    for (int i = 1; i < d; i++) u.m[i][i - 1] = 1;
    for (; t; t >>= 1, u = u*u) if (t & 1) r = r*u;
    printf("%d", r.m[0][0]);
    return 0;
}

11070번: Pythagorean Expectation

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

구현문제

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

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, u, v, p, q, t;
int main() {
    for (scanf("%d", &t); t--;) {
        int s[1001] = {}, a[1001] = {}, maxi = 0, mini = 1e3;
        for (scanf("%d%d", &n, &m); m--;) {
            scanf("%d%d%d%d", &u, &v, &p, &q);
            s[u] += p; a[u] += q;
            s[v] += q; a[v] += p;
        }
        for (int i = 1; i <= n; i++) {
            int w = s[i] ? s[i] * s[i] * 1000LL / (s[i] * s[i] + a[i] * a[i]) : 0;
            if (w > maxi) maxi = w;
            if (w < mini) mini = w;
        }
        printf("%d\n%d\n", maxi, mini);
    }
    return 0;
}

11067번: Monotone Walkway

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

x값이 다른 두 점에 대해서는 x값이 작은 점들의 번호가 작아야 한다. x가 같은 점들의 번호 순서는, 해당 x값보다 작으면서 가장 큰 번호의 점을 찾고 이 번호의 y값을 시작으로 오름차순 혹은 내림차순 정렬해서 매기면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, n, m, x;
pair<int, int> p[100001];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
        sort(p + 1, p + 1 + n);
        for (int i = 1, e; i < n; i = e) {
            e = upper_bound(p + 1, p + 1 + n, make_pair(p[i].first, int(1e9))) - p;
            if (p[i].second^p[i - 1].second) reverse(p + i, p + e);
        }
        for (scanf("%d", &m); m--;) scanf("%d", &x), printf("%d %d\n", p[x].first, p[x].second);
    }
    return 0;
}

11062번: Card Game

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

c[i]: i번째 카드에 쓰인 수
dp[i][j]: j-i+1, j-i+2, ..., j번째 카드가 남았을 때 선수 플레이어가 만들 수 있는 최대 합
dp[i][j] = sum(c[k]: j-i<k<=j) - min(dp[i-1][j-1],dp[i-1][j])

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

#include<cstdio>
#include<algorithm>
using namespace std;
int s[1001], n, t;
int main() {
    for (scanf("%d", &t); t--;) {
        int dp[1001] = {};
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
        for (int i = 1; i <= n; i++) for (int j = n; j >= i; j--) dp[j] = s[j] - s[j - i] - min(dp[j - 1], dp[j]);
        printf("%d\n", dp[n]);
    }
    return 0;
}

6064번: Cain Calendar

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

d = GCD(m,n)
확장 유클리드 알고리즘을 이용해 mu - nv = y-x (n/d > u >= 0, m/d > v >= 0)인 u, v를 찾는다.

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

#include<cstdio>
#include<algorithm>
int n, m, x, y, t;
int ee(int a, int b, int &u, int &v) {
    if (!b) {
        u = 1;
        v = 0;
        return a;
    }
    int ret = ee(b, a%b, v, u);
    v -= a / b*u;
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d%d", &m, &n, &x, &y);
        int u, v, ret = ee(m, -n, u, v);
        if ((y - x) % ret) { puts("-1"); continue; }
        int p = abs(n / ret);
        printf("%d\n", (u*(y - x) / ret%p + p) % p*m + x);
    }
    return 0;
}

13510번: 트리와 쿼리 1

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

HLD를 구현한다.

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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int last[100001], idx[100001], cnt[100001], par[100001], tree[400000], c;
int n, m, u[100000], v[100000], w[100000];
vector<int> adj[100001];
void count(int h, int p) {
    for (int it : adj[h]) if (it^p) count(it, h), cnt[h] += cnt[it];
    cnt[h]++;
}
void build(int h, int p) {
    int t = 0;
    for (int it : adj[h]) if (it^p && cnt[t] < cnt[it]) t = it;
    for (int it : adj[h]) if (it^p && it^t) build(it, h);
    if (!last[h]) last[h] = h;
    if (t) last[t] = last[h], build(t, h);
    par[h] = p;
    idx[h] = ++c;
}
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) tree[h] = x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
        tree[h] = max(tree[h * 2 + 1], tree[h * 2 + 2]);
    }
}
int query(int h, int l, int r, int gl, int gr) {
    if (gr < l || r < gl) return 0;
    if (gl <= l&&r <= gr) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int lca(int x, int y) {
    int ret = 0;
    while (last[x] ^ last[y]) {
        if (cnt[last[x]] > cnt[last[y]]) swap(x, y);
        ret = max(ret, query(0, 1, n, idx[x], idx[last[x]]));
        x = par[last[x]];
    }
    if (cnt[x] > cnt[y]) swap(x, y);
    return max(ret, query(0, 1, n, idx[x], idx[y] - 1));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", u + i, v + i, w + i);
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    count(1, 0);
    build(1, 0);
    for (int i = 1; i < n; i++) {
        if (par[v[i]] == u[i]) swap(u[i], v[i]);
        update(0, 1, n, idx[u[i]], w[i]);
    }
    scanf("%d", &m);
    for (int i = 0, q, x, y; i < m; i++) {
        scanf("%d%d%d", &q, &x, &y);
        if (q == 1) update(0, 1, n, idx[u[x]], y);
        else printf("%d\n", lca(x, y));
    }
    return 0;
}

11378번: 열혈강호 4

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

이분 매칭 문제로 만들어 풀 수 있다.
먼저, 직원과 일을 일대일 매칭시킨다. 그리고 나서 벌점을 배분하는데, 매칭이 되지 않은 일 중 해당 일을 할 수 있는 직원(처음에 매칭되었던 직원이라도 상관없다.)이 있다면 그러한 직원 아무에게나 1점의 벌점을 매기고 해당 일을 하도록 할 수 있다.
고로 답은 min( (일대일 매칭 수) + k, (직원 누군가 할 수 있는 일의 개수) )

시간복잡도는 $O(V^3)$ // V = n+m

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int vis[1001], rev[1001], n, m, k, ck[1001], cnt, c;
vector<int> adj[1001];
int dfs(int h) {
    vis[h] = c;
    for (int it : adj[h]) if (!rev[it] || vis[rev[it]] ^ c && dfs(rev[it])) {
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= n; i++) for (scanf("%d", &x); x--;) {
        scanf("%d", &y);
        adj[i].push_back(y);
        cnt += !ck[y]++;
    }
    for (c = 1; c <= n; c++) k += dfs(c);
    printf("%d", min(k, cnt));
    return 0;
}

1786번: 찾기

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

kmp 알고리즘을 구현한다.

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

#include<cstdio>
#include<vector>
using namespace std;
char t[1000001], p[1000001];
int pi[1000001] = { -1 };
vector<int> res;
int main() {
    scanf("%[^\n]%*c%[^\n]", t, p);
    for (int i = 0, j = -1; p[i]; pi[++i] = ++j) while (~j && p[i] ^ p[j]) j = pi[j];
    for (int i = 0, j = 0; t[i]; i++) {
        while (~j && t[i] ^ p[j]) j = pi[j];
        if (!p[++j]) res.push_back(i + 2 - j);
    }
    printf("%d\n", res.size());
    for (int it : res) printf("%d ", it);
    return 0;
}

1708번: 볼록 껍질

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

graham scan을 이용한다.

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

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> point;
long long ccw(point i, point j, point k) {
    return 1LL * (j.x - i.x)*(k.y - i.y) - 1LL * (k.x - i.x)*(j.y - i.y);
}
int n, sz;
point p[100000], stk[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    swap(p[0], *min_element(p, p + n));
    sort(p + 1, p + n, [](point i, point j) {
        long long t = ccw(p[0], i, j);
        return t > 0 || !t&&i < j;
    });
    for (int i = 0; i < n; i++) {
        while (sz > 1 && ccw(stk[sz - 2], stk[sz - 1], p[i]) <= 0) sz--;
        stk[sz++] = p[i];
    }
    printf("%d", sz);
    return 0;
}

위, 아래 껍질을 나눠서 구할 수도 있다.

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

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> point;
point p[100000], low[100000], up[100000];
int n, sl, su;
long long ccw(point i, point j, point k) {
    return 1LL * (j.x - i.x)*(k.y - i.y) - 1LL * (k.x - i.x)*(j.y - i.y);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        while (sl > 1 && ccw(low[sl - 2], low[sl - 1], p[i]) >= 0) sl--;
        while (su > 1 && ccw(up[su - 2], up[su - 1], p[i]) <= 0) su--;
        low[sl++] = up[su++] = p[i];
    }
    printf("%d", sl + su - 2);
    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;
}