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

11498번: Odd Cycle

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

#include<cstdio>
#include<vector>
using namespace std;
int tc, n, m, ck[100001], valid[100001], cl[100001], flag[100001];
vector<int> adj[2][100001], vis;
void dfs(int h, int ty) {
    if (ck[h] ^ ty) return;
    ck[h] = !ty;
    for (auto &it : adj[ty][h]) dfs(it, ty);
    vis.push_back(h);
}
vector<int> via, via2;
bool dfs3(int h) {
    if (flag[h]) {
        int i = 0;
        while (via[i] ^ h) i++;
        printf("1\n%d\n", via2.size() + via.size() - i);
        for (auto &it : via2) printf("%d\n", it);
        for (; i < via.size(); i++) printf("%d\n", via[i]);
        return true;
    }
    int tt = valid[h];
    valid[h] = -1;
    via2.push_back(h);
    for (auto &it : adj[0][h]) if (valid[it] == tt && cl[it] - cl[h] & 1) {
        if (dfs3(it)) return true;
    }
    via2.pop_back();
    return false;
}
bool dfs2(int h) {
    via.push_back(h);
    flag[h] = 1;
    for (auto &it : adj[0][h]) if (valid[it] == valid[h]) {
        if (!~cl[it]) {
            cl[it] = cl[h] + 1;
            if (dfs2(it)) return true;
        }
        else if (cl[h] + 1 - cl[it] & 1) {
            via2.clear();
            dfs3(it);
            return true;
        }
    }
    via.pop_back();
    flag[h] = 0;
    return false;
}
int main() {
    for (scanf("%d", &tc); tc--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            adj[0][i].clear();
            adj[1][i].clear();
            valid[i] = cl[i] = -1;
            ck[i] = 0;
        }
        for (int i = 0, x, y; i < m; i++) {
            scanf("%d%d", &x, &y);
            adj[0][x].push_back(y);
            adj[1][y].push_back(x);
        }
        vis.clear();
        for (int i = 1; i <= n; i++) dfs(i, 0);
        vector<int> tvis = vis;
        int rr = 0;
        for (int i = n; i--;) if (ck[tvis[i]]) {
            vis.clear();
            dfs(tvis[i], 1);
            for (auto &it : vis) valid[it] = i, flag[it] = 0;
            cl[vis[0]] = 0;
            via.clear();
            if (dfs2(vis[0])) { rr = 1; break; }
        }
        if (!rr) puts("-1");
    }
    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;
}

11695번: 표 게임

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

i번째 행에 있는 돌의 합을 si라 놓자. 그러면 이들을 이용하는 님게임으로 생각할 수 있다.
si를 모두 xor 시켰을 때 0이면 선수 승리, 1이면 후수 승리.

#include<cstdio>
int n, m;
long long s, r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        s = 0;
        for (int j = 0, x; j < m; j++) scanf("%d", &x), s += x;
        r ^= s;
    }
    puts(r ? "august14" : "ainta");
    return 0;
}

5386번: Doubloon Game

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

#include<cstdio>
int s, k, t;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &s, &k);
        if (k & 1) printf("%d\n", s & 1);
        else {
            s %= k + 1;
            printf("%d\n", s / k*k + s % 2);
        }
    }
    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;
}