A: 문자열 패턴 확인 주어진 문자열에서 '1', '2', '3'의 등장 횟수를 세어, 각각 1개, 2개, 3개인지 검사한다. 이를 위해 배열을 사용해 각 숫자의 빈도를 저장하고 조건을 비교한다.

#include <iostream>
#include <string>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int cnt[4] = {};
    for (char c : s) cnt[c - '0']++;
    if (cnt[1] == 1 && cnt[2] == 2 && cnt[3] == 3)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

B: 구분자 기준 분할 문자열을 '|'로 나누어 각 부분의 길이를 계산한다. 순서대로 출력하며, 맨 처음은 비어 있을 수 있으므로 주의한다.

#include <iostream>
#include <string>
using namespace std;

void solve() {
    string s;
    cin >> s;
    int len = 0;
    for (char c : s) {
        if (c == '|') {
            if (len > 0) cout << len << ' ';
            len = 0;
        } else {
            len++;
        }
    }
    if (len > 0) cout << len;
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

C: 연속된 블록 교환 연속된 0 또는 1의 블록을 크기와 값으로 분리하여 리스트로 저장한다. 주어진 인덱스에 해당하는 1블록과 그 앞의 0블록을 교체한다. 이후 다시 문자열로 복원하여 출력한다.

#include <iostream>
#include <string>
using namespace std;

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s = ' ' + s;
    vector<pair<int, int>> blocks;
    int cur = s[1] - '0', count = 1;
    
    for (int i = 2; i <= n; ++i) {
        if (s[i] - '0' == cur) {
            count++;
        } else {
            blocks.push_back({cur, count});
            cur = s[i] - '0';
            count = 1;
        }
    }
    blocks.push_back({cur, count});

    int target = 0;
    for (int i = 0; i < blocks.size(); ++i) {
        if (blocks[i].first == 1) {
            target++;
            if (target == k) {
                swap(blocks[i], blocks[i-1]);
                break;
            }
        }
    }

    for (auto& [val, cnt] : blocks) {
        for (int j = 0; j < cnt; ++j)
            cout << val;
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

D: 반전 패턴 탐색 문자열이 반복되며 점점 더 많은 반전이 적용되는 구조이다. 주어진 위치 (k)가 어느 복제본에 속하는지 찾고, 그 복제본의 반전 여부를 결정한다. 이는 이진 표현의 최상위 비트와 1의 개수를 통해 계산 가능하다.

#include <iostream>
#include <string>
using namespace std;

char flip(char c) {
    return islower(c) ? toupper(c) : tolower(c);
}

int lowbit(int x) { return x & -x; }

bool query(int pos, const string& s) {
    int len = s.size();
    long long block = pos / len;
    int idx = pos % len;
    if (idx == 0) idx = len;
    else --block;

    int b = 0, c = 0;
    while (block) {
        b += block & 1;
        block >>= 1;
    }
    int msb = 1;
    while (msb <= block) msb <<= 1;
    msb >>= 1;
    c = 0;
    while (msb) {
        if (block & msb) c++;
        msb >>= 1;
    }

    bool flipped = (c & 1) ^ ((b - 1) & 1);
    return flipped ? flip(s[idx - 1]) : s[idx - 1];
}

void solve() {
    string s;
    int q;
    cin >> s >> q;
    while (q--) {
        long long k;
        cin >> k;
        cout << query(k, s) << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

E: 색상 변경과 집합 관리 배열의 일부를 색으로 변경할 때, 인접한 동일 색 영역을 합쳐야 하므로, 유니온 파인드를 활용한다. 각 집합의 시작/끝 지점, 색, 크기를 유지하며, 색이 같아지는 경우 병합한다. 쿼리마다 특정 위치의 집합 크기를 반환한다.

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 500005;
int fa[MAXN], sz[MAXN], col[MAXN], left_bound[MAXN], right_bound[MAXN];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    fa[x] = y;
    sz[y] += sz[x];
    left_bound[y] = min(left_bound[y], left_bound[x]);
    right_bound[y] = max(right_bound[y], right_bound[x]);
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        sz[i] = 1;
        col[i] = i;
        left_bound[i] = right_bound[i] = i;
    }

    while (q--) {
        int op, x, c;
        cin >> op >> x;
        if (op == 1) {
            cin >> c;
            int root = find(x);
            sz[col[x]] -= sz[root];
            col[x] = c;
            sz[c] += sz[root];
            if (left_bound[root] > 1 && col[find(left_bound[root]-1)] == c)
                merge(left_bound[root]-1, x);
            if (right_bound[root] < n && col[find(right_bound[root]+1)] == c)
                merge(right_bound[root]+1, x);
        } else {
            cout << sz[col[find(x)]] << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

F: 상태 압축 및 메모이제이션 카드는 세 사람(타카하시, 아오키, 테이블)에게 배분될 수 있으며, 상태는 3진수로 표현된다. 메모이제이션을 사용한 재귀 탐색으로 승패를 판단한다. 각 상태에서 가능한 모든 행동을 시뮬레이션하며, 상대방의 승리 여부에 따라 현재 플레이어의 결과를 결정한다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 15, M = 6000000;
int n, m, l;
int cards[N + M + L];
int pow3[N + M + L];
int memo[2][M];

int get_state(int st, int idx) {
    return (st / pow3[idx]) % 3;
}

int update_state(int st, int idx, int new_val) {
    return st - (get_state(st, idx) * pow3[idx]) + new_val * pow3[idx];
}

bool dfs(int player, int state) {
    if (memo[player][state] != -1) return memo[player][state];
    int cnt = 0;
    for (int i = 0; i < n + m + l; ++i)
        if (get_state(state, i) == player) ++cnt;
    if (cnt == 0) return memo[player][state] = false;

    bool result = false;
    for (int i = 0; i < n + m + l; ++i) {
        if (get_state(state, i) != player) continue;
        int next = update_state(state, i, 2);
        if (!dfs(player ^ 1, next)) {
            result = true;
            break;
        }
        for (int j = 0; j < n + m + l; ++j) {
            if (get_state(state, j) != 2 || cards[j] >= cards[i]) continue;
            int new_state = update_state(next, j, player);
            if (!dfs(player ^ 1, new_state)) {
                result = true;
                break;
            }
        }
        if (result) break;
    }
    return memo[player][state] = result;
}

void solve() {
    cin >> n >> m >> l;
    pow3[0] = 1;
    for (int i = 1; i < n + m + l; ++i) pow3[i] = pow3[i-1] * 3;
    int state = 0;
    for (int i = n; i < n + m; ++i) state += pow3[i];
    for (int i = n + m; i < n + m + l; ++i) state += 2 * pow3[i];
    for (int i = 0; i < n + m + l; ++i) cin >> cards[i];
    memset(memo, -1, sizeof(memo));
    if (dfs(0, state))
        cout << "Takahashi\n";
    else
        cout << "Aoki\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

G: 확률 기반 역순쌍 계산 배열을 세 구간으로 나누고, 중간 (k) 길이 구간은 무작위로 섞임. 전체 역순쌍의 기댓값은 전체 역순쌍 수에서 중간 구간의 실제 역순쌍 수를 빼고, 무작위 섞었을 때의 기댓값 (\frac{k(k-1)}{4})를 더한다. 슬라이딩 윈도우 방식으로 중간 구간의 역순쌍 수를 업데이트하며, 트리 제이트를 이용해 효율적으로 처리한다.

#include
#include
using namespace std;

typedef long long ll;
const int MAXN = 200005, MOD = 998244353;

ll modpow(ll a, ll b, ll mod) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

struct BIT {
vector tree;
int n;
BIT(int size) : n(size), tree(size + 1, 0) {}
void add(int i, ll v) {
for (; i <= n; i += i & -i) tree[i] += v;
}
ll query(int i) {
ll sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
ll range_query(int l, int r) {
return query(r) - query(l - 1);
}
};

int n, k;
ll a[MAXN];

void solve() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];

BIT bit(n);
ll total_inv = 0;
for (int i = 1; i <= n; ++i) {
total_inv += bit.query(a[i] - 1);
bit.add(a[i], 1);
}

bit = BIT(n);
ll window_inv = 0;
for (int i = 1; i <= k; ++i) {
window_inv += bit.query(a[i] - 1);
bit.add(a[i], 1);
}

ll ans = (total_inv - window_inv) % MOD;
for (int i = 2; i <= n - k + 1; ++i) {
bit.add(a[i-1], -1);
window_inv -= bit.query(a[i-1] - 1);
window_inv += bit.range_query(a[i+k-1] + 1, n);
bit.add(a[i+k-1], 1);
ans += total_inv - window_inv;
ans %= MOD;
}

ans = ans * modpow(n - k + 1, MOD - 2, MOD) % MOD;
ans = (ans + (k * (k - 1) / 2) % MOD * modpow(4, MOD - 2, MOD)) % MOD;
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}