A. 공 던지기
간단한 시뮬레이션으로 해결할 수 있다. 현재 위치에서 지시에 따라 좌우로 이동하며, 처음 방문하는 지점의 개수를 기록하면 된다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
string s;
cin >> n >> s;
vector<bool> seen(n);
int pos = 0, distinct = 1;
seen[0] = true;
for (char ch : s) {
pos += (ch == 'R' ? 1 : -1);
if (!seen[pos]) {
seen[pos] = true;
distinct++;
}
}
cout << distinct << "\n";
}
return 0;
}B. 오른쪽 최댓값
前綴 최댓값을 활용한 시뮬레이션이다. 각 단계에서 현재 구간의 최댓값을 찾아, 그 최댓값이 마지막으로 등장하는 위치까지의 후미를 제거하는 과정을 반복한다. 제거되는 구간은 한 번만 순회하므로 전체 복잡도는 선형이다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1), pref(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = max(pref[i - 1], a[i]);
}
int ops = 0, curLen = n;
while (curLen > 0) {
int target = pref[curLen];
while (curLen > 0 && a[curLen] != target) curLen--;
curLen--; ops++;
}
cout << ops << "\n";
}
return 0;
}C. 봄
포함-배제 원리를 적용한다. 세 수열의 각 항에 대해 독립적으로 계산하며, 개별 항목, 두 항목의 최소공배수, 세 항목의 최소공배수를 고려하여 보정한다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll x, y, z, lim;
cin >> x >> y >> z >> lim;
ll ab = lcm(x, y), ac = lcm(x, z), bc = lcm(y, z), abc = lcm(ab, z);
ll base = 6 * (lim / x);
ll resX = base;
resX -= 3 * (lim / ab) + 3 * (lim / ac);
resX += 2 * (lim / abc);
ll resY = 6 * (lim / y);
resY -= 3 * (lim / ab) + 3 * (lim / bc);
resY += 2 * (lim / abc);
ll resZ = 6 * (lim / z);
resZ -= 3 * (lim / ac) + 3 * (lim / bc);
resZ += 2 * (lim / abc);
cout << resX << " " << resY << " " << resZ << "\n";
}
return 0;
}D. 교차 경로
그래프의 각 연결 요소를 분석한다. 홀수 길이의 사이클이 존재하면 해당 연결 요소의 모든 정점은 "완벽한 정점"이 될 수 없다. 사이클이 없으면 이분 그래프로 볼 수 있으며, DFS 트리에서 이의 홀수/짝수 레벨 중 더 큰 쪽을 선택하면 된다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<int> depth;
int compSize, oddDepth;
bool dfs(int u, int p) {
compSize++;
if (depth[u] % 2) oddDepth++;
bool valid = true;
for (int v : adj[u]) {
if (v == p) continue;
if (depth[v]) {
if ((depth[u] - depth[v] + 1) % 2) valid = false;
} else {
depth[v] = depth[u] + 1;
valid &= dfs(v, u);
}
}
return valid;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
adj.assign(n + 1, {});
depth.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (depth[i]) continue;
compSize = oddDepth = 0;
depth[i] = 1;
if (dfs(i, 0)) {
ans += max(oddDepth, compSize - oddDepth);
}
}
cout << ans << "\n";
}
return 0;
}E. 자릿수 합 (반복)
자릿수 합 함수의 반복 적용은 매우 빠르게 한 자리 수收斂한다. 가능한 모든 목표값을 미리 계산하고, 각 목표값에 대해 필요한 숫자 분포를 기록해둔다. 이후 주어진 문자열로 해당 분포를 만들 수 있는지, 남은 숫자들의 합이 목표값과 일치하는지 확인한다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
int need[900005][10];
bool feasible(int target, const array<int, 10>& have) {
int leftoverSum = 0, leftoverCnt = 0;
for (int d = 0; d < 10; d++) {
if (have[d] < need[target][d]) return false;
leftoverCnt += have[d] - need[target][d];
leftoverSum += (have[d] - need[target][d]) * d;
}
return leftoverCnt == 0 || leftoverSum == target;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 2; i <= 900000; i++) {
int x = i;
while (x >= 10) {
int s = 0, t = x;
while (t > 0) {
need[i][t % 10]++;
s += t % 10;
t /= 10;
}
x = s;
}
need[i][x]++;
}
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int n = s.size();
if (n == 1) {
cout << s << "\n";
continue;
}
array<int, 10> freq{};
for (char c : s) freq[c - '0']++;
int chosen = 0;
for (int v = 2; v <= 900000; v++) {
if (feasible(v, freq)) {
chosen = v;
break;
}
}
for (int d = 9; d >= 0; d--) {
int rem = freq[d] - need[chosen][d];
while (rem-- > 0) cout << d;
}
while (true) {
cout << chosen;
if (chosen < 10) break;
int nxt = 0, tmp = chosen;
while (tmp > 0) {
nxt += tmp % 10;
tmp /= 10;
}
chosen = nxt;
}
cout << "\n";
}
return 0;
}F. 분수의 합
구간에서 가장 작은 분모를 가진 분수가 전체 합을 결정하므로, 단조 스택으로 각 위치가 최솟값이 되는 구간 범위를 구한다. 이후 쿼리별로 증가 횟수에 따른 분류를 통해 차분 배열로 구간 갱신을 수행한다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
ll power(ll a, ll b) {
ll r = 1;
a %= MOD;
while (b > 0) {
if (b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n + 1), q(m + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> q[i];
vector<int> leftBound(n + 1), rightBound(n + 1);
vector<int> stk;
stk.push_back(0);
for (int i = 1; i <= n; i++) {
while (stk.size() > 1 && a[stk.back()] > a[i]) stk.pop_back();
leftBound[i] = stk.back();
stk.push_back(i);
}
stk.clear();
stk.push_back(n + 1);
for (int i = n; i >= 1; i--) {
while (stk.size() > 1 && a[stk.back()] >= a[i]) stk.pop_back();
rightBound[i] = stk.back();
stk.push_back(i);
}
ll baseAns = 0;
for (int i = 1; i <= n; i++) {
ll notMinL = (ll)i * (n - rightBound[i] + 1) % MOD;
ll notMinR = (ll)leftBound[i] * (n - i + 1) % MOD;
ll notMinBoth = (ll)leftBound[i] * (n - rightBound[i] + 1) % MOD;
ll notMin = (notMinL + notMinR - notMinBoth + MOD) % MOD;
baseAns = (baseAns + notMin * power(a[i], MOD - 2)) % MOD;
}
vector<ll> coeff1(m + 2), coeff2(m + 2), countSum(m + 2);
for (int i = 1; i <= n; i++) {
ll ways = (ll)(i - leftBound[i]) * (rightBound[i] - i) % MOD;
int pos = lower_bound(q.begin() + 1, q.begin() + m + 1, a[i]) - q.begin() - 1;
ll invA = power(a[i], MOD - 2);
ll add1 = invA * ways % MOD;
coeff1[1] = (coeff1[1] + add1) % MOD;
coeff1[pos + 1] = (coeff1[pos + 1] - add1 + MOD) % MOD;
ll add2 = (MOD - a[i] % MOD) * ways % MOD;
coeff2[pos + 1] = (coeff2[pos + 1] + add2) % MOD;
countSum[pos + 1] = (countSum[pos + 1] + ways) % MOD;
}
for (int i = 1; i <= m; i++) {
coeff1[i] = (coeff1[i] + coeff1[i - 1]) % MOD;
coeff2[i] = (coeff2[i] + coeff2[i - 1]) % MOD;
countSum[i] = (countSum[i] + countSum[i - 1]) % MOD;
}
for (int i = 1; i <= m; i++) {
ll part1 = coeff1[i] * (q[i] + 1) % MOD;
ll part2 = (coeff2[i] + (q[i] + 2) %MOD * countSum[i]) % MOD;
cout << (part1 + part2 + baseAns) % MOD << "\n";
}
return 0;
}