A - 지역 예선 선택 도박
문제 요약
총 $k$개의 경기가 있으며, 각 경기마다 대학당 최대 $c_i$개 팀이 참가 가능하다. $n$개 팀이 있고 각 팀은 점수와 소속 대학 정보를 가진다. 각 팀은 최대 2개 경기에 출전할 수 있다. 모든 팀이 최악의 상황에서 얻을 수 있는 최선의 순위를 구해야 한다.
핵심 아이디어
최악의 경우는 내가 참가하는 경기에 강팀들이 몰리는 상황이다. 순위를 높이려면 정원이 적은 경기를 선택해야 한다. 2개 경기에 나갈 수 있지만, 최악의 경우 두 경기 모두 강팀이 따라오므로 결국 한 경기만 고려하면 된다.
구현
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Team {
int idx;
int score;
string univ;
bool operator<(const Team& o) const {
return score > o.score;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
int minCap = INT_MAX;
for (int i = 0; i < k; i++) {
int cap; cin >> cap;
minCap = min(minCap, cap);
}
vector<Team> teams(n);
for (int i = 0; i < n; i++) {
cin >> teams[i].score >> teams[i].univ;
teams[i].idx = i;
}
sort(teams.begin(), teams.end());
unordered_map<string, int> used;
vector<int> res(n);
int rank = 0;
for (auto& t : teams) {
if (used[t.univ] < minCap) {
rank++;
used[t.univ]++;
}
res[t.idx] = rank;
}
for (int x : res) cout << x << '\n';
return 0;
}
F - 관광객
문제 요약
초기값 1500에서 시작하여 $n$개의 정수를 순서대로 더한다. 합이 4000 이상이 되는 최소 시점을 출력하고, 불가능하면 -1을 출력한다.
풀이
단순 누적 합 계산이다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, cur = 1500;
cin >> n;
for (int i = 0; i < n; i++) {
int add; cin >> add;
cur += add;
if (cur >= 4000) {
cout << i + 1 << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
G - 도박 게임
문제 요약
A와 B가 게임을 한다. 초기 칩은 각각 $x, y$개이고, A가 이길 확률은 $p_0$, B가 이길 확률은 $p_1$, 무승부 확률은 $1-p_0-p_1$이다. 무승부 시 즉시 다음 판, 승자의 칩이 패자의 칩 이상이면 종료, 패자는 승자의 현재 칩 수만큼 잃는다. A의 최종 승리 확률을 구한다.
핵심 아이디어
$x=y$, $x<y$, $x>y$ 세 경우로 나뉜다. 유클리드 호제법과 유사한 재귀로 해결하며, 호출 횟수는 제한적이다. $x>y$인 경우 B가 연속으로 $cnt$번 이길 확률 $P_B$를 계산하고, 그 후 재귀적으로 처리한다.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 998244353;
int64 power(int64 base, int64 exp) {
int64 res = 1;
while (exp > 0) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
int64 probA, probB;
int64 solve(int64 a, int64 b) {
if (a == b) return probA;
if (a < b) {
int64 cnt = b / a;
if (b % a == 0) cnt--;
return solve(a, b - a * cnt) * power(probA, cnt) % MOD;
}
int64 cnt = a / b;
if (a % b == 0) cnt--;
int64 sub = solve(a - b * cnt, b);
return ((sub - 1 + MOD) % MOD * power(probB, cnt) % MOD + 1) % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 x, y, a, b, c;
cin >> x >> y >> a >> b >> c;
int64 denom = a + b;
probA = a * power(denom, MOD - 2) % MOD;
probB = b * power(denom, MOD - 2) % MOD;
int T; cin >> T;
while (T--) {
cout << solve(x, y) << '\n';
}
return 0;
}
I - 특이한 이진수
문제 요약
음이 아닌 정수 $n$이 주어졌을 때, $\sum_{i=0}^{31} 2^i \cdot a_i = n$을 만족하는 수열 $A$를 찾는다. 단 $a_i \in \{-1, 0, 1\}$이고 연속한 두 원소가 모두 0이면 안 된다.
핵심 아이디어
$a_{31}=1$이어야 음수가 안 된다. $01$ 패턴은 $1,-1$로 변환 가능하며, 이를 통해 $2^i = 2^{i+1} - 2^i$로 재구성한다. 연속된 0이 2개 이상이면 불가능하다.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
int64 n; cin >> n;
vector<int> coeff(32);
int pos = 0;
while (n > 0) {
coeff[pos++] = n & 1;
n >>= 1;
}
for (int i = 0; i <= 30; i++) {
if (coeff[i] == 1 && coeff[i+1] == 0) {
coeff[i+1] = 1;
coeff[i] = -1;
}
}
bool ok = true;
for (int i = 0; i < 31; i++) {
if (coeff[i] == 0 && coeff[i+1] == 0) {
ok = false;
break;
}
}
if (!ok) {
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 0; i <= 31; i++) {
cout << coeff[i] << (i % 8 == 7 ? '\n' : ' ');
}
}
return 0;
}
J - 화물 적재
문제 요약
$n$개 물품이 있고 각각 무게 $w$, 부피 $v$, 압축률 $c$를 가진다. 적재 후 물품 $i$의 부피는 $v_i - c_i \cdot W_i$이며, $W_i$는 위 물품들의 무게 합이다. 총 부피 합의 최솟값을 구한다.
핵심 아이디어
근접 교환법으로 $\frac{c}{w}$ 오름차순이 최적임을 증명한다. 두 물품을 바꿀 때 부피 변화량 $\Delta v = -c_i w_{i+1} + c_{i+1} w_i$이므로, $\frac{c_i}{w_i} < \frac{c_{i+1}}{w_{i+1}}$이면 $\Delta v > 0$이다.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Item {
int64 w, v, c;
bool operator<(const Item& o) const {
return c * o.w < o.c * w;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<Item> items(n);
int64 total = 0;
for (auto& it : items) {
cin >> it.w >> it.v >> it.c;
total += it.v;
}
sort(items.begin(), items.end());
int64 weightSum = 0;
for (auto& it : items) {
total -= weightSum * it.c;
weightSum += it.w;
}
cout << total << '\n';
return 0;
}
L - 502 Bad Gateway
문제 요약
값 $T$가 주어지고, 매 단계에서 1을 빼거나 $[1, T)$ 범위로 재설정할 수 있다. 0이 되는 최소 기대 횟수를 분수로 출력한다.
핵심 아이디어
임계값 $c$를 정해 $c$ 미만이 될 때까지 재설정, 이후 1씩 감소하는 전략이 최적이다. 기대값은 $\frac{c-1}{2} + \frac{T}{c}$이며, $c \approx \sqrt{2T}$에서 최소가 된다.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int64 gcd(int64 a, int64 b) {
return b ? gcd(b, a % b) : a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
int64 t; cin >> t;
int64 c1 = (int64)ceil(sqrt(2.0 * t));
int64 c2 = (int64)floor(sqrt(2.0 * t));
auto calc = [&](int64 c) -> pair<int64, int64> {
int64 num = 2 * t + c * (c - 1);
int64 den = 2 * c;
int64 g = gcd(num, den);
return {num / g, den / g};
};
auto [n1, d1] = calc(c1);
auto [n2, d2] = calc(c2);
if (n1 * d2 < n2 * d1) {
cout << n1 << ' ' << d1 << '\n';
} else {
cout << n2 << ' ' << d2 << '\n';
}
}
return 0;
}
대회 링크: Codeforces Gym 105358