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

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

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

10257번: Stains

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

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int t, m, n, c, st[1001][10], dp[1001][60000];
vector<int> cd;
int f(int h, int b) {
    if (h > n) return 0;
    int &ret = dp[h][b];
    if (~ret) return ret;
    int ck[10] = {};
    ret = 1e9;
    for (int &it : cd) {
        int cnt = 0, flag = 0, nxt = 0;
        for (int i = b, j = 0; j < m; i /= 3, j++) ck[j] = i % 3;
        for (int i = 0; i < m - 2; i++) if (1 << i&it) {
            cnt++;
            for (int j = i; j < i + 3; j++) ck[j] = 3;
        }
        for (int i = m; i--;) {
            if (st[h][i] && !ck[i]) flag = 1;
            if (ck[i]) ck[i]--;
            nxt = nxt * 3 + ck[i];
        }
        if (!flag) ret = min(ret, cnt + f(h + 1, nxt));
    }
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d", &m, &n, &c);
        cd.clear();
        memset(dp, -1, sizeof(dp));
        memset(st, 0, sizeof(st));
        for (int i = 1 << m - 2; i--;) {
            int flag = 0;
            for (int j = 1; j < m - 3; j++) if (1 << j & i && 1 << j - 1 & i) flag = 1;
            for (int j = 2; j < m - 3; j++) if (1 << j & i && 1 << j - 2 & i) flag = 1;
            if (flag) continue;
            cd.push_back(i);
        }
        for (int i = 0, x, y; i < c; i++) {
            scanf("%d%d", &x, &y);
            st[y][x - 1] = 1;
        }
        printf("%d\n", f(1, 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;
}

11064번: Diameter

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

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, d;
int main() {
    for (scanf("%d", &t); t--;) {
        vector<pair<int, int> > adj[40001];
        priority_queue<pair<int, int> > pq;
        int r = 0, t = 0, cnt = 0, ind[40001] = {};
        scanf("%d%d", &n, &d);
        for (int i = 1, x, y, z; i < n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[x].push_back({ y,z });
            adj[y].push_back({ x,z });
            r += z;
            ind[x]++;
            ind[y]++;
        }
        for (int i = 1; i <= n; i++) if (ind[i] == 1) pq.push({ -adj[i][0].second,i }), cnt++;
        for (;;) {
            int h = pq.top().second, dis = -pq.top().first;
            pq.pop();
            if (2 * dis >= d) {
                printf("%.1lf\n", r - (d / 2.0 - t) * cnt);
                break;
            }
            r -= (dis - t)*cnt--;
            if (cnt == 1) {
                puts("0.0");
                break;
            }
            ind[h]--;
            for (auto u : adj[h]) if (--ind[u.first] == 1) {
                for (auto v : adj[u.first]) if (ind[v.first]) pq.push({ -dis - v.second,u.first }), cnt++;
            }
            t = dis;
        }
    }
    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;
}