[ICPC] Latin America Regional 2017 일부 문제 풀이

A. Arranging Tiles

BOJ 15052번: https://www.acmicpc.net/problem/15052

이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전처리해두었다면, 여기서 최소를 구하는 건 TSP 문제로 환원되므로 비트마스크 DP를 통해 $O(2^N)$에 처리해줄 수 있습니다.

모든 다각형은 윗쪽과 아랫쪽 변에 맞닿은 평행한 선분을 포함하고 있으니, 이 선분 두 개를 기점으로 왼쪽과 오른쪽 점들을 따로 떼서 분리해 보면 Convex Hull의 Left hull과 Right Hull로 바꿀 수 있습니다. 따라서 실제로 붙일 수 있는 최대 길이를 계산할 때는 왼쪽 다각형의 Right Hull과, 오른쪽 다각형의 Left Hull만 확인해 주면 됩니다. 이 두 Hull에 대해서 붙일 수 있는 최대 길이는 모든 y축에 평행한 직선에 대해서 Right/Left Hull과의 교점을 각각 $p$와 $q$라고 했을 때, $x_q - x_p$의 최솟값이 됩니다(그림을 그려 보면 자명하게 알 수 있습니다). 다음 사실을 이용해서 최솟값을 빠르게 구해줄 수 있습니다.

• y좌표에 대한 이 함수의 값은 Convex합니다.

이 함수는 결과적으로 각 다각형 길이의 합에서 Right Hull과 Left Hull에 해당하는 값을 빼 준 값을 나타내는 함수인데, 이 두 Hull에 해당하는 값이 항상 Convex하므로 Convex한 함수의 합과, 이런 함수에 상수를 곱한 함수는 Convex하다는 성질에 따라서 위 성질을 가지게 됩니다. 따라서 그 함수에 대해 삼분탐색을 해 줄 수도 있고, y=0부터 y=h까지 스위핑하면서 만나는 점이 생길때마다 매번 확인해주어도 됩니다. 삼분탐색을 하게 된다면 각 Hull을 y축 기준으로 정렬해두고 현재 보고 있는 y좌표에 해당하는 선분이 무엇인지를 이분 탐색을 통해 빠르게 찾아야 합니다. 두 Hull의 원소 개수 $P$와 $Q$에 대해 전자의 경우 복잡도는 $O(\log _3 H \lg P \lg Q)$가 되고, 후자의 경우는 $O(P+Q)$가 됩니다. 이 값들을 모두 전처리해두면 그 뒤는 TSP로 해결해줄 수 있습니다.

저는 $O(N^2 \log _3 H \lg P \lg Q + 2^N)$으로 코딩했습니다. 입력량이 많기 때문에 double로 입력받으면 느리고, int로 입력받은 다음에 형변환을 해 주어야 합니다. 저는 FastIO를 사용했습니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#include <unistd.h>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
#define double long double
/*#define cin file_in
#define cout file_out*/

using namespace std;

namespace io {
    const signed IS = 1 << 22;
    char I[IS + 1], * J = I;

    inline void daer() { if (J >= I + IS - 64) { char* p = I; do*p++ = *J++; while (J != I + IS); p[read(0, p, I + IS - p)] = 0; J = I; } }
    template<int N = 10, typename T = int>inline T getu() { daer(); T x = 0; int k = 0; do x = x * 10 + *J - '0'; while (*++J >= '0' && ++k < N); ++J; return x; }
    template<int N = 10, typename T = int>inline T geti() { daer(); bool e = *J == '-'; J += e; return(e ? -1 : 1) * getu<N, T>(); }
    struct f { f() { I[read(0, I, IS)] = 0; } }flu;
};
using namespace io;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

//중요하지 않은 기하 라이브러리는 생략합니다.

inline int diff(double lhs, double rhs) {
    if (lhs - eps < rhs && rhs < lhs + eps) return 0;
    return (lhs < rhs) ? -1 : 1;
}
bool get_cross(const Line& a, const Line& b, Point& ret) {
    double mdet = outer(b.dir, a.dir);
    if (diff(mdet, 0) == 0) return false;
    double t2 = outer(a.dir, b.pos - a.pos) / mdet;
    ret = b.pos + b.dir * t2;
    return true;
}

struct Polygon {
    double l, xmin = 1e9, xmax = -1e9;
    vector<Point> L, R;
};

Point readpt() {
    int t1, t2;
    t1 = geti<10>();
    t2 = geti<10>();
    return {(double)t1,(double)t2 };
}

int n;
Polygon p[20];
double w[20][20], H;

double my_intersect(double t, vector<Point>& vr, vector<Point>& vl, double rmax, double lmin) {
    Point tp = { 1e9, t };
    int ridx = lower_bound(all(vr), tp) - vr.begin();
    int lidx = lower_bound(all(vl), tp) - vl.begin();
    if (ridx == 0 || ridx == vr.size() || lidx == 0 || lidx == vl.size()) return 0;
    Line rline, lline;

    rline = { vr[ridx],  vr[ridx - 1] - vr[ridx] }, lline = { {0,t}, {1,0} };
    Point rit;
    if (!get_cross(rline, lline, rit)) return 0;

    rline = { vl[lidx], vl[lidx - 1] - vl[lidx] }, lline = { {0,t}, {1,0} };
    Point lit;
    if (!get_cross(rline, lline, lit)) return 0;

    return abs(rit.x-rmax) + abs(lit.x-lmin);
}

void calculate(int u, int v) {
    double l = eps, r = H - eps, lm, rm;
    for (int i = 0; i < 100; i++) {
        lm = (l * 2 + r) / 3;
        rm = (l + r * 2) / 3;
        double lx = my_intersect(lm, p[u].R, p[v].L,p[u].xmax,p[v].xmin);
        double rx = my_intersect(rm, p[u].R, p[v].L,p[u].xmax, p[v].xmin);
        if (lx < rx) r = rm;
        else l = lm;
    }
    w[u][v] = my_intersect(l, p[u].R, p[v].L, p[u].xmax, p[v].xmin);
}

double cache[20][1 << 15];

double dp(int h, int bit) {
    if (bit == (1 << n) - 1) return 0;
    double& ret = cache[h][bit];
    if (ret > -0.5) return ret;
    double ma = -1;
    for (int i = 0; i < n; i++) {
        if (bit & (1 << i)) continue;
        ma = max(dp(i, bit | (1 << i)) + w[h][i], ma);
    }
    return ret = ma;
}

int main() {
    n = geti<10>();
    double sum = 0;
    for (int i = 0; i < n; i++) {
        int t; t = geti<10>();
        Point at = readpt();
        Point lpt = { -1e9,-1e9 };
        int chk = 0; 
        for (int j = 1; j < t; j++) {
            Point hpt = readpt();
            if (!diff(hpt.y, lpt.y)) {
                chk = j;
                p[i].L.push_back(hpt);
                break;
            }
            p[i].R.push_back(hpt);
            lpt = hpt;
        }
        for (int j = chk + 1; j < t; j++) {
            Point hpt = readpt();
            p[i].L.push_back(hpt);
        }
        p[i].L.push_back(at);

        for (auto h : p[i].L) {
            p[i].xmin = min(p[i].xmin, h.x);
            p[i].xmax = max(p[i].xmax, h.x);
            H = max(H, h.y);
        }
        for (auto h : p[i].R) {
            p[i].xmin = min(p[i].xmin, h.x);
            p[i].xmax = max(p[i].xmax, h.x);
            H = max(H, h.y);
        }
        sort(all(p[i].L));
        sort(all(p[i].R));
        p[i].l = p[i].xmax - p[i].xmin;
        sum += p[i].l;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            calculate(i, j);
        }
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j < (1 << 15); j++) cache[i][j] = -1;

    double ma = -1;
    for (int i = 0; i < n; i++) {
        ma = max(ma, dp(i, 1 << i));
    }
    cout << fixed;
    cout << setprecision(3);
    cout << sum - ma;
    return 0;
}

D. Daunting Device

BOJ 15055번: https://www.acmicpc.net/problem/15055

정해는 소각로(https://www.acmicpc.net/problem/15901)와 유사한 방법을 사용하지만, 훨씬 쉬운 풀이가 있어서 소개합니다.

쿼리를 처리하는 문제에서 자주 사용하는 Sqrt Decomposition을 이용합니다. 수열을 버킷 $B = \sqrt{L}$개로 쪼갭시다. 우리는 전체 수열에 대해 각 원소가 몇 개 존재하는지를 저장하는 배열을 최신으로 관리해 줄 것입니다. 거기에 더해, 각 버킷이 만약 동일한 수로 완전히 덮혀 있다면 이 또한 어떤 수로 덮여 있는지를 기록해서 역시 최신으로 관리해주도록 합시다.

어떤 쿼리가 들어오면, 각 원소가 몇 개 존재하는지를 항상 최신으로 관리해준다고 했으니 쿼리의 업데이트 범위를 구해줄 수 있습니다. 그 다음 실제로 업데이트를 하면 되는데, 구간에 완전히 포함되는 버킷은 Lazy Propagation을 하는 것처럼 어떤 수로 덮겠다라고만 기록하고, 갱신해주면 됩니다. 만약 기존에도 버킷 전체가 같은 수로 덮여 있었다면 Lazy 값만 갱신해주면 되므로 버킷 당 $O(1)$에 되고, 그게 아니라면 직접 어떤 원소들이 삭제되는지를 확인해야 하므로 $O(B)$에 수행해야 합니다. 마찬가지로 구간에 완전히 포함되지 않는 버킷은 Lazy를 실제로 적용시켜 준 다음 일일히 처리해줌으로서 $O(B)$에 처리할 수 있습니다. 이 경우 기존에 Lazy가 있었다고 해도 그 Lazy 값이 풀려 없어져 버립니다.

언뜻 보면 최악의 경우에 확인하는 모든 버킷에 대해 $O(B)$가 걸리니 쿼리당 $O(B^2)$이 걸린다고 착각할 수 있습니다. 하지만 처음에 원소는 모두 1로 채워져 있으므로 Lazy가 1인 것으로 간주할 수 있고, 업데이트를 할 때마다 Lazy는 최대 2개의 버킷에서만 제거됩니다(완전히 구간에 포함되지 않는 끄트머리 버킷 2개). 결과적으로 문제를 모두 풀 때까지 Lazy가 없는 버킷은 최대 $2B$개 정도만 만들어지고, 이 Lazy가 없는 버킷은 똑같이 Lazy가 없는 버킷으로 덮어씌워지거나 한번 $O(B)$ 시간으로 처리한 후에는 다시 Lazy 값이 생겨 $O(1)$에 처리할 수 있기 때문에 전체 쿼리에 대해 각 쿼리당 amortized $O(B)$에 처리할 수 있습니다.

마지막에 한번 배열을 순회하면서 정답을 구해주면 됩니다. 총 시간복잡도는 $O(N\sqrt{L}+C)$입니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int l, c, n, m;
int a[101010], r[101010], b[300], bs[300];
const int sz = 400;

void query() {
    int P, x;
    ll A, B;
    cin >> P >> x >> A >> B;

    ll S = a[P];
    ll m1 = (A + S * S) % l;
    ll m2 = (A + (S + B) * (S + B)) % l;
    if (m1 > m2) swap(m1, m2);

    int b1 = m1 / sz, b2 = m2 / sz;
    if (b1 == b2) {
        if(b[b1] != -1) for (int i = sz * b1; i < sz * b1 + bs[b1]; i++) r[i] = b[b1];
        for (int i = m1; i <= m2; i++) {
            a[r[i]]--;
            r[i] = x;
            a[r[i]]++;
        }
        b[b1] = -1;
    }
    else {
        for (int i = b1 + 1; i <= b2 - 1; i++) {
            if (b[i] != -1) {
                a[b[i]] -= bs[i];
                b[i] = x;
                a[b[i]] += bs[i];
            }
            else {
                for (int j = sz * i; j < sz * i + bs[i]; j++) {
                    a[r[j]]--;
                    r[j] = x;
                    a[r[j]]++;
                }
                b[i] = x;
            }
        }
        if (b[b1] != -1) for (int i = sz * b1; i < sz * b1 + bs[b1]; i++) r[i] = b[b1];
        for (int i = m1; i < b1 * sz + bs[b1]; i++) {
            a[r[i]]--;
            r[i] = x;
            a[r[i]]++;
        }
        if (b[b2] != -1) for (int i = sz * b2; i < sz * b2 + bs[b2]; i++) r[i] = b[b2];
        for (int i = b2 * sz; i <= m2; i++) {
            a[r[i]]--;
            r[i] = x;
            a[r[i]]++;
        }
        b[b1] = b[b2] = -1;
    }
}

int main() {
    fio();
    cin >> l >> c >> n;

    m = (l - 1) / sz + 1;
    for (int i = 0; i < m; i++) {
        b[i] = 1;
        bs[i] = i != m - 1 ? sz : l % sz;
    }
    a[1] = l;
    for (int i = 0; i < l; i++) r[i] = 1;

    for (int i = 0; i < n; i++)
        query();

    int ma = 0;
    for (int i = 1; i <= c; i++) ma = max(ma, a[i]);
    cout << ma;
    return 0;
}

G. Gates of Uncertainty

BOJ 15058번: https://www.acmicpc.net/problem/15058

트리 DP를 합니다. $DP[x][a][b]$를 정점 $x$에서, stuck이 없을 때 $a$가 출력되고 stuck이 있을 때 $b$가 출력되는 경우의 수라고 합시다. 만약 $x$가 외부 입력이라면 $a=b$일 경우는 1이고 아닌 경우에는 0입니다. $x$가 외부 입력이 아니라면 왼쪽 자식과 오른쪽 자식에 대해 경우의 수 4가지씩, 총 $4 \times 4 =16$가지 경우를 모두 봐 주면서 stuck이 없는 경우와 있는 경우에 대해 적절히 상태를 전이해주면 됩니다. 말로 설명하는 것 보다, 코드를 보는 게 훨씬 빠릅니다. 시간복잡도는 $O(16N)$입니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

ll add(ll a, ll b) {
    return (a + b) % LMOD;
}
ll sub(ll a, ll b) {
    return (a - b + LMOD) % LMOD;
}
ll mul(ll a, ll b) {
    return (a * b) % LMOD;
}

struct node {
    int x, y, f;
};

node a[101010];
int rc[101010], root;
ll dp[101010][2][2];
const int k[2][2] = { {1,1}, {1,0} };

void dfs(int h) {
    if (!h) return;
    dfs(a[h].x);
    dfs(a[h].y);

    int l = a[h].x, r = a[h].y;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
             ll tmp = mul(dp[l][i / 2][i % 2], dp[r][j / 2][j % 2]);
             int idx = a[h].f == -1 ? k[i % 2][j % 2] : a[h].f;
             ll& st = dp[h][k[i / 2][j / 2]][idx];
             st = add(st, tmp);
        }
    }
}

int main() {
    fio();
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t1, t2, t3; cin >> t1 >> t2 >> t3;
        a[i] = { t1,t2,t3 };
        rc[t1]++; rc[t2]++;
    }
    for (int i = 1; i <= n; i++)
        if (!rc[i]) root = i;
    dp[0][0][0] = dp[0][1][1] = 1;
    dp[0][1][0] = dp[0][0][1] = 0;
    dfs(root);
    cout << add(dp[root][1][0], dp[root][0][1]);
    return 0;
}

I. Imperial Roads

BOJ 15060번: https://www.acmicpc.net/problem/15060

MST를 찾아둡시다. 어떤 간선 $(u,v)$가 추가되면, 스패닝 트리를 유지하기 위해 제거해야 하는 간선은 MST에서 $u$와 $v$를 잇는 경로 위에 있는 간선 중 하나입니다. 따라서 그 중 제일 가중치가 큰 것을 뽑아 버려주면 됩니다. 트리 위에서 경로 중 최댓값을 찾는 것은 Sparse Table이나 Heavy Light Decomposition으로 해줄 수 있고, 시간복잡도는 각각의 경우 $O(E \lg E + Q\lg N)$ 또는 $O(E \lg E + Q \lg ^2 N)$입니다. 저는 Sparse Table을 사용했습니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

struct UnionFind {
    vector<int> par;
    UnionFind(int _n) : par(_n + 1) {
        for (int i = 0; i <= _n; i++) par[i] = i;
    }
    int fi(int x) {
        if (x == par[x]) return x;
        else return par[x] = fi(par[x]);
    }
    void un(int a, int b) {
        a = fi(a); b = fi(b);
        if (a == b) return;
        par[a] = b;
    }
};

int n, m;
int dep[101010], par[101010][20], dist[101010][20];
vector<pii> adj[101010];

void dfs(int x, int p, int d) {
    dep[x] = d;
    par[x][0] = p;
    for (auto th : adj[x]) {
        if (th.first == p) continue;
        dfs(th.first, x, d + 1);
    }
}

void process() {
    dist[1][0] = -1;
    dfs(1, 1, 1);
    for (int i = 1; i <= n; i++) {
        for (auto [u, c] : adj[i]) {
            if (dep[i] < dep[u]) dist[u][0] = c;
            else dist[i][0] = c;
        }
    }
    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
            dist[j][i] = max(dist[j][i-1],dist[par[j][i - 1]][i - 1]);
        }
    }
}

int lca(int p, int q) {
    if (dep[p] > dep[q]) swap(p, q);
    int k = dep[q] - dep[p];
    for (int i = 19; i >= 0; i--)
        if (k & (1 << i)) q = par[q][i];
    if (p == q) return p;
    for (int i = 19; i >= 0; i--) {
        if (par[p][i] == par[q][i]) continue;
        p = par[p][i], q = par[q][i];
    }
    return par[p][0];
}

int query(int x, int y) {
    int k = dep[x] - dep[y];
    int ma = 0;
    for (int i = 19; i >= 0; i--) {
        if (k & (1 << i)) {
            ma = max(ma, dist[x][i]);
            x = par[x][i];
        }
    }
    return ma;
}

int main() {
    fio();
    cin >> n >> m;
    vector<tpi> ed;
    map<pii, int> M;
    for (int i = 0; i < m; i++) {
        int t1, t2, t3; cin >> t1 >> t2 >> t3;
        ed.emplace_back(t3, t1, t2);
        if (t1 > t2) swap(t1, t2);
        M[make_pair(t1, t2)] = t3;
    }
    sort(all(ed));

    ll s = 0;
    UnionFind uf(n + 1);
    for (auto [cost,u,v] : ed) {
        if (uf.fi(u) == uf.fi(v)) continue;
        s += cost;
        uf.un(u, v);
        adj[u].emplace_back(v, cost);
        adj[v].emplace_back(u, cost);
    }
    process();
    int q; cin >> q;
    while (q--) {
        int t1, t2; cin >> t1 >> t2;
        if (t1 > t2) swap(t1, t2);
        int l = lca(t1, t2);
        cout << s + M[make_pair(t1,t2)] - max(query(t1, l), query(t2, l)) << endl;
    }
    return 0;
}

J. Jumping Frog

BOJ 15061번: https://www.acmicpc.net/problem/15061

돌이 N개 있을 때, 밟는 돌은 항상 $\gcd (N,K)$개 간격입니다. $N$과 임의의 수의 최대공약수로 나올 수 있는 수들은 반드시 $N$의 약수이고, 이 수들의 개수는 $\displaystyle N^{-3}$에 비례합니다. 따라서 이 후보들에 대해서만 계산해줘도 무방합니다. 결국 뛸 때 밟는 돌들의 번호는 $K$로 나눈 나머지가 같은 돌들이므로, 하나의 $K$에 대해서 계산하는 것은 $O(N)$으로 쉽게 할 수 있습니다. 결과적으로 시간복잡도는 $O(N^\frac{4}{3})$이 됩니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int chk[101010];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    fio();
    string s; cin >> s;
    memset(chk, -1, sizeof(chk));
    int n = s.length(), a = 0;
    for (int i = 1; i < n; i++) {
        int h = gcd(n, i);
        if (chk[h] != -1) {
            a += chk[h];
            continue;
        }
        int t = 0;
        vector<int> v(h);
        for (int j = 0; j < n; j++)
            if (s[j] == 'P') v[j % h] = 1;
        for (int j = 0; j < h; j++)
            if (!v[j]) t = 1;
        chk[h] = t;
        a += t;
    }
    cout << a;
    return 0;
}

M. Marblecoin

BOJ 15064번: https://www.acmicpc.net/problem/15064

잘 생각해보면 먼저 훔친 구슬은 나중에 훔친 구슬보다 반드시 더 큰 영향력을 발휘하므로, 훔친 구슬의 순서를 사전순 최소로 만드는 것과 다르지 않습니다. 따라서 문제는 $N$개의 스택에서 적절히 구슬을 빼서 사전순 최소인 수열을 찾은 다음, 그 수열의 롤링 해시값을 구하는 것으로 바꿀 수 있습니다.

너무나도 당연하게 다음과 같은 그리디를 생각해볼 수 있습니다. 구슬이 1개 이상 남아 있는 모든 스택 중 top에 있는 원소가 가장 작은 스택에서 원소를 하나 빼내오는 것을 반복합니다. 만약 원소가 가장 작은 스택이 여러개라면, 스택의 바로 뒤에 있는 원소가 더 작은 것을 고릅니다. 이는 priority queue를 이용해서 빠르게 반복해 줄 수 있지만, 두 스택이 거의 다 같은 원소로 구성될 수 있으므로 스택끼리 우선순위를 비교하는 데 최악의 경우 $O(K)$ 시간이 걸립니다.

문제를 해결하는 핵심적인 아이디어는 각 스택을 문자열로 간주하는 것입니다. 그렇게 된다면 스택은 앞에서부터만 원소가 제거되므로 우리가 위 알고리즘에서 비교하게 되는 모든 스택은 맨 처음 스택이 나타내는 문자열의 접미사로 생각할 수 있습니다. 따라서 Suffix Array를 계산해 둔다면 두 스택을 빠르게 비교할 수 있게 되어 문제를 쉽게 해결할 수 있습니다.

시간복잡도는 $\displaystyle \sum_{i=1}^{N} K_i = X$라고 할 때 $O(X \lg X + X \lg N) = O(X \lg X)$가 됩니다.

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
#define fileio() ifstream file_in("input.txt");ofstream file_out("output.txt")
/*#define cin file_in
#define cout file_out*/

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;

const int MOD = 1000000007;
const ll LMOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };


typedef int T;

//Please Open Testdata 팀의 팀노트에서 가져왔습니다. 출처: https://github.com/ntopia/icpc-teamnote/blob/master/teamnote.pdf

vector<int> suffix_array(const vector<T>& in) {
    int n = (int)in.size(), c = 0;
    vector<int> temp(n), pos2bckt(n), bckt(n), bpos(n), out(n);
    for (int i = 0; i < n; i++) out[i] = i;
    sort(out.begin(), out.end(), [&](int a, int b) { return in[a] < in[b]; });
    for (int i = 0; i < n; i++) {
        bckt[i] = c;
        if (i + 1 == n || in[out[i]] != in[out[i + 1]]) c++;
    }
    for (int h = 1; h < n && c < n; h <<= 1) {
        for (int i = 0; i < n; i++) pos2bckt[out[i]] = bckt[i];
        for (int i = n - 1; i >= 0; i--) bpos[bckt[i]] = i;
        for (int i = 0; i < n; i++)
            if (out[i] >= n - h) temp[bpos[bckt[i]]++] = out[i];
        for (int i = 0; i < n; i++)
            if (out[i] >= h) temp[bpos[pos2bckt[out[i] - h]]++] = out[i] - h;
        c = 0;
        for (int i = 0; i + 1 < n; i++) {
            int a = (bckt[i] != bckt[i + 1]) || (temp[i] >= n - h)
                || (pos2bckt[temp[i + 1] + h] != pos2bckt[temp[i] + h]);
            bckt[i] = c;
            c += a;
        }
        bckt[n - 1] = c++;
        temp.swap(out);
    }
    return out;
}

vector<int> s;
vector<pii> v[101010];

int main() {
    fio();
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int m, t; cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> t;
            s.push_back(t);
        }
        s.push_back(301);
    }
    auto sat = suffix_array(s);
    vector<int> sa(s.size());
    for (int i = 0; i < s.size(); i++)
        sa[sat[i]] = i;

    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 301) cnt++;
        else v[cnt].emplace_back(sa[i], s[i]);
    }

    priority_queue<pii, vector<pii>, greater<pii>> Q;
    for (int i = 0; i < n; i++) {
        reverse(all(v[i]));
        Q.emplace(v[i].back().first, i);
    }

    ll sum = 0;
    while (!Q.empty()) {
        auto h = Q.top(); Q.pop();
        ll r = v[h.second].back().second;
        sum += r;
        sum *= 365;
        sum %= LMOD;
        v[h.second].pop_back();
        if (!v[h.second].empty()) Q.emplace(v[h.second].back().first, h.second);
    }
    cout << sum;
    return 0;
}