By MilkClouds in PS — 2021년 8월 22일

KickStart Round E 2021 풀이

KickStart Round E 2021

100등대였으나 2번째 문제를 이상하게 삽질하다 못 풀고 결국 200등대로 밀려났다.

1. Shuffled Anagrams

얼핏 보기에 쉬워 보이나 깔끔하게 풀기 위한 아이디어 도출이 생각보다 어려웠던 문제다. 문자열을 정렬한 후, 빈도가 최대인 문자의 빈도를 구하고, 그 빈도만큼 전체 문자열을 shift시킨다. i번째 문자가 있으면 k만큼 shift 시킨 후 i+k에 위치하게 될 것이다. shift시키기 전의 i번째 문자와 shift시킨 후의 i번째 문자는 IMPOSSIBLE인 경우가 아니라면 다 다를 것이라고 기대할 수 있다. 발생 빈도가 c인 어떤 문자 S가 있을 때 shift를 c보다 작게 시키면 충돌이 일어나나 shift를 c 이상으로 시키면 S가 모두 S가 있던 영역을 벗어나 겹치지 않게 되기 때문이다.

전체 매핑 과정후에 모순이 생긴다면 IMPOSSIBLE, 아니라면 완성된 문자열을 출력하면 된다. 아마도 전체 문자열 길이의 1/2를 기준으로 이것보다 한 문자의 빈도수가 많으면 IMPOSSIBLE일 것이라 추측하긴 했으나 혹시 틀릴까봐 그냥 naive하게 전체 문자열을 검토하도록 구현했다. 공식 풀이에서는 N/2만큼 shift시킨 풀이를 소개했는데, 생각했던 대로 N/2가 경계선인 듯하다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;

string solve(){
    string S;
    cin >> S;
    vector<pair<char, int>> A;
    vector<int> cnt(26);
    string T(S.size(), 1);
    rep(i, 0, S.size()) A.eb(S[i], i), cnt[S[i] - 'a']++;
    sort(all(A));
    int bias = *max_element(all(cnt));
    rep(i, 0, S.size()){
        T[A[i].y] = A[(i + bias) % S.size()].x;
    }
    rep(i, 0, S.size()) if(S[i] == T[i]) return "IMPOSSIBLE";
    return T;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
    int TC;
    cin >> TC;
    rep(tc, 0, TC){
        cout << "Case #" << tc + 1 << ": " << solve() << "\\n";
    }
}

2. Birthday Cake

전체 크기가 n*m이고 모든 영역이 delicious한 케이크가 있다고 하자. 이때 칼이 충분히 길면 n(m-1)+n-1=nm-1번 잘라서 모든 영역을 분리 가능하다.

만약 칼이 좀 짧으면 floor((n-1)/k) * floor((m-1)/k)개의 격자점에 칼 길이 늘리는 테이프를 배치해서 해결할 수 있다.

따라서 delicious 영역의 테두리를 제외하고 내부를 나누기 위해서는 nm-1+floor((n-1)/k) * floor((m-1)/k)번 케이크를 잘라야 한다.

테두리의 경우 케이크 가장 외곽에 있는 경우와 아닌 경우, 그리고 최외각에서 delicious한 영역에 도달하기 위해 필요한 칼 사용 등을 고려해 계산하면 된다.

솔직히 스코어보드 보고 1,3,4번 푼 사람들도 거의 대부분이 2번을 못 풀었길래 엄청 어려운 문제인 줄 알았다. O(1) 문제인 줄 알았으면 쉽게 풀었을지도.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;

const ll INF = numeric_limits<ll>::max();
ll R, C, K, a, b, c, d, n, m;
ll calc(pi a){
    return (a.x + K - 1) / K - (a.y + K - 1) / K;
}
ll solve(){
    cin >> R >> C >> K;
    cin >> a >> b >> c >> d; a--; b--;
    n = c - a;
    m = d - b;
    ll ans = n * m - 1 + ((n - 1) / K) * ((m - 1) / K), tmp = 0, ret = INF;
    if(a) tmp += (m + K - 1) / K;
    if(b) tmp += (n + K - 1) / K;
    if(c < R) tmp += (m + K - 1) / K;
    if(d < C) tmp += (n + K - 1) / K;
    if(a && c < R){
        ret = min(ret, min(calc({d, m}), calc({C - b, m})));
    }
    if(b && d < C){
        ret = min(ret, min(calc({c, n}), calc({R - a, n})));
    }
    if(ret == INF) ret = 0;
    return ans += ret + tmp;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
    int TC;
    cin >> TC;
    rep(tc, 0, TC){
        cout << "Case #" << tc + 1 << ": " << solve() << "\\n";
    }
}

3. Palindromic Crossword

같은 글자가 들어가야 할 위치들을 DSU로 묶는다. 묶는 과정에서 .가 아니라 확정된 알파벳 글자가 나타난다면 그 글자를 해당 dsu tree에(alpha[root]에) 저장해 놓는다.
모든 노드에 대해 해당 노드의 dsu tree의 알파벳을 출력한다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;

const int MAX = 1111;
int N, M, vis[MAX][MAX], cnt;
char S[MAX][MAX];
vector<int> R[MAX], C[MAX];
struct DSU {
// if u is root : par[u] = -(size of tree)// else: par[u] = parent of upublic:
    DSU() : N(0) {}
    explicit DSU(int N) : N(N), par(N, -1), alpha(N, '.') {}
    int merge(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        u = find(u); v = find(v);
        if (u == v) return u;
        if (-par[u] < -par[v]) swap(u, v);
        alpha[u] = max(alpha[u], alpha[v]);
        par[u] += par[v];
        par[v] = u;
        return u;
    }
    int find(int u) {
        assert(0 <= u && u < N);
        if (par[u] < 0) return u;
        return par[u] = find(par[u]);
    }
    bool same(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        return find(u) == find(v);
    }
    int size(int u) {
        assert(0 <= u && u < N);
        return -par[find(u)];
    }
    vector<vector<int> > groups() {
        vector<int> roots(N), groups(N);
        for (int i = 0; i < N; i++) {
            roots[i] = find(i);
            groups[roots[i]]++;
        }
        vector<vector<int> > result(N);
        for (int i = 0; i < N; i++) {
            result[i].reserve(groups[i]);
        }
        for (int i = 0; i < N; i++) {
            result[roots[i]].push_back(i);
        }
        result.erase(
            remove_if(result.begin(), result.end(), [&](const vector<int>& v) { return v.empty(); }), result.end()
        );
        return result;
    }
    int N;
    vector<int> par;
    vector<char> alpha;
} dsu;

inline int conv(int i, int j){
    return (i - 1) * M + (j - 1);
}

void dfs(int i, int j){
    if(S[i][j] == '#' || S[i][j] != '.') return;
    if(vis[i][j] == 1) return;
    vis[i][j] = 1;
    auto rj = lower_bound(all(R[i]), j);
    auto lj = rj - 1;
    auto ri = lower_bound(all(C[j]), i);
    auto li = ri - 1;
    char& ans = S[i][j];
    for(auto [nx, ny]: {pi(i, *lj + *rj - j), pi(*li + *ri - i, j)}){
        if(vis[nx][ny] == 0){
            dsu.merge(conv(i, j), conv(nx, ny));
            dfs(nx, ny);
        }
    }
}
void solve(){
    cin >> N >> M;

    cnt = 0;
    fill(vis[0], vis[N + 2], 0);
    rep(i, 0, N + 1) R[i].clear();
    rep(j, 0, M + 1) C[j].clear();
    dsu = DSU(N * M);

    rep(i, 1, N + 1) cin >> (S[i] + 1), S[i][0] = S[i][M + 1] = '#';
    rep(i, 1, N + 1) rep(j, 1, M + 1) dsu.alpha[conv(i, j)] = S[i][j];
    rep(j, 0, M + 2) S[0][j] = S[N + 1][j] = '#';
    rep(i, 0, N + 2) rep(j, 0, M + 2){
        if(S[i][j] == '#') R[i].eb(j);
    }
    rep(j, 0, M + 2) rep(i, 0, N + 2){
        if(S[i][j] == '#') C[j].eb(i);
    }
    rep(i, 1, N + 1) rep(j, 1, M + 1) dfs(i, j);

    rep(i, 1, N + 1) rep(j, 1, M + 1) cnt += dsu.alpha[dsu.find(conv(i, j))] != S[i][j];

    cout << cnt << "\\n";
    rep(i, 1, N + 1) {
        rep(j, 1, M + 1) cout << dsu.alpha[dsu.find(conv(i, j))];
        cout << "\\n";
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
    int TC;
    cin >> TC;
    rep(tc, 0, TC){
        cout << "Case #" << tc + 1 << ": "; solve();
    }
}

4. Increasing Sequence Card Game

임의의 수열이 존재할 때, 앞에 나왔던 원소보다 작은 원소는 무시하자. 이때 원래 수열의 길이가 N이었다면 작업 후 수열의 길이의 기댓값을 구하는 문제다.

아직 문제를 안 풀었으면 풀이를 읽어보지 않는 것을 추천한다. 소스코드 아래에 풀이를 더 쓰겠다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define rep2(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define em emplace
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define x first
#define y second
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using pl = pair<ll, ll>;
using tl = tuple<ll, ll, ll>;

const ll MAX = 1e6;
long double solve(){
    ll N;
    cin >> N;
    long double tmp = 0;
    rep(i, 1, min(MAX, N) + 1){
        tmp += (long double) 1 / i;
    }
    return N >= MAX ? logl(N / MAX) + tmp : tmp;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false); cout.tie(0);
    int TC;
    cin >> TC;
    cout << fixed; cout.precision(18);
    rep(tc, 0, TC){
        cout << "Case #" << tc + 1 << ": " << solve() << "\\n";
    }
}

풀이를 말해보자면, 식을 세워서 기댓값을 정리하다 보면 조화급수가 나온다. 조화급수는 10^6부터는 1/x의 적분으로 계산하면 1e-6 이하의 오차로 계산할 수 있다.

KickStart Round E 2021 풀이