대회 오픈컨 당일에 사정상 참여할 수 없어 뒤늦게 시간재고 풀어보는 시간을 가졌다.
오픈컨은 7시간동안 15문제였던 것으로 기억하는데, 7시간 내내 ps에 시간투자하긴 어려울 듯하여, 14~17시동안 Master 8문제를 해결해보는 시간을 가졌다.
진행 방식: 그룹 연습 / 티어: 성공한 문제에만 표시 / 알고리즘 분류: 보지 않음. / 그 전에 해결한 문제: 없음.
오픈컨 참가한 사람들에게는 solvedac 캐릭터가 판교역 옆에 서있는 배경을 주던데, 나는 오픈컨 참여는 하지 못했기 때문에 받지 못했다.
간단하게 후기를 작성해보겠다.
23738. A - Ресторан
대문자로 이루어진 문자열을 입력받으면 소문자로 바꿔주되, 특정 문자는 별도로 replace해주어야 하는 문제였다.
크게 어렵지 않은데, if문으로 노가다하는 데에 시간을 잡아먹는 문제.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M;
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'B')
cout << 'v';
else if (s[i] == 'E')
cout << "ye";
else if (s[i] == 'H')
cout << 'n';
else if (s[i] == 'P')
cout << 'r';
else if (s[i] == 'C')
cout << 's';
else if (s[i] == 'Y')
cout << 'u';
else if (s[i] == 'X')
cout << 'h';
else cout << (char)(s[i] - 'A' + 'a');
}
}tag: 브론즈2, 문자열, 구현
개인적으로 생각하는 태그랑 현재 태그랑 일치한다.
23739. B - 벼락치기
30분 동안 벼락치기를 하고, 쉬었다가 다시 30분간 벼락치기를 하고 쉬었다가를 반복하는 구현 문제이다.
30분이 끝나면 다음 챕터로 넘어가버린다는 점에서 조금 까다로울 수 있다고 생각한다.
남은 시간동안 챕터를 끝낼 수 있으면 끝내고 다음 챕터로 넘어간다.
만약 다 끝내지는 못하되, 절반 이상 끝낼 수 있다면 ans를 증가시키고 이번 시간 공부는 끝낸다.
다 끝내지도 못하고 절반 이상도 못끝낸다면 ans를 증가시키지 않고 이번 시간 공부는 끝내도록 한다.
또한, ti가 홀수일 때, 절반 이상 공부했는지 소수점 버림 때문에 잘못 판단할 수 있기 때문에 double형을 이용해주었다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 111;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, ans;
double a[MAX];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
}
double t = 30.0;
for (int i = 0; i < N; i++) {
if (t - a[i] >= 0) {
ans++;
t -= a[i];
if (t <= 0)
t = 30.0;
}
else if (t >= a[i] / 2) {
ans++;
t = 30.0;
}
else {
t = 30.0;
}
}
cout << ans;
}태그: 브론즈1, 수학, 구현
개인적으로는 실버5~4 정도로 생각한다.
23740. C - 버스 노선 개편하기
전형적인 스위핑, 투포인터 문제.
먼저 시작점이 빠른 순대로 노선들을 정렬해주자.
그 다음, 차례대로 스위핑하면서 노선이 겹치는지 여부를 판단해주면 된다.
정말 기본적인건데, 끝점은 max(끝점, 현재노선의 끝점)으로 해주어야 max값이 나온다.
max를 하지 않고 끝점 = 현재노선의 끝점 으로 하면 WA를 받는다. (내가 그랬기 때문이다..)
스위핑이 끝난 후에 마지막 공통노선을 집어넣어주는 것도 잊지 말자.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<ll, ll> pl;
const int MAX = 200011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M;
vector<pii> v, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++) {
int s, e, c;
cin >> s >> e >> c;
v.push_back({ { s,e }, c });
}
sort(all(v));
int s = 0, e = 0, c = 0;
for (int i = 0; i < v.size(); i++) {
int left = v[i].first.first;
int right = v[i].first.second;
int cost = v[i].second;
if (!i) {
s = left;
e = right;
c = cost;
continue;
}
if (left <= e) {
e = max(e, right);
s = min(s, left);
c = min(c, cost);
}
else {
ans.push_back({ {s,e},c });
s = left;
e = right;
c = cost;
}
}
ans.push_back({ {s,e},c });
sort(all(ans));
press(ans);
cout << ans.size() << "\n";
for (auto i : ans) {
cout << i.first.first << " " << i.first.second << " " << i.second << "\n";
}
}태그: 골드5, 구현, 정렬, 스위핑
나도 골드5 정도라 생각한다.
23741. D - 야바위 게임
처음에는 dp로 하려 했지만, DAG가 아니기 때문에 빠른 포기.
바로 DFS가 생각나 dfs코드를 짜던 중, 어차피 경우에 따라 여러 갈래로 나뉘며, 특정 횟수가 되면 종료되기 때문에 bfs로 빠르게 풀면 되겠다 싶어 bfs로 작성하였다.
그리고, 특정 횟수에 따른 방문처리를 위해 배열을 vis[위치][움직인 횟수]로 잡아주었다.
나중에 생각해보니까 그냥 vis[위치][홀/짝 여부]로 판단하면 되는 문제... 움직이는 횟수(Y)가 작아서 다행이었다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M, X, Y;
vector<int> v[MAX], ans;
bool vis[MAX][MAX];
void bfs() {
queue<pi> q;
q.push({ 0, X });
vis[X][0] = true;
while (!q.empty()) {
int cur = q.front().second;
int t = q.front().first;
q.pop();
if (t == Y) {
ans.push_back(cur);
continue;
}
for (auto i : v[cur]) {
if (!vis[i][t + 1] && t + 1 <= Y) {
vis[i][t + 1] = true;
q.push({ t + 1, i });
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M >> X >> Y;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
bfs();
sort(all(ans));
press(ans);
if (ans.empty())
cout << -1;
else {
for (auto i : ans) {
cout << i << " ";
}
}
}23742. E - Player-based Team Distribution
사실 ai>=0이면 최대한 많이, ai<0이면 팀이 아닌 개인을 이루도록 해서
단순히 ai>=0인 사람 수 세주고, 간단하게 해주면 되는 문제 아닌가 했는데 그렇게 단순하지 않았다.
어떤 팀 A의 점수합이 a, 인원 수가 m이라 하고, 어떤 팀 B의 점수합이 b, 인원 수가 n이라 하자.
팀이 따로일 때 받을 수 있는 점수는 am+bn이고, 합칠 때 받을 수 있는 점수는 (a+b)(m+n) = am+bn + an + bm이다.
즉, 팀을 합치는 경우가 팀이 따로일 때 받을 수 있는 점수보다 an + bm 점을 더 받을 수 있는 것이다.
따라서 a, b가 둘 다 양수일 경우는 합치는게 무조건 이득이다.
a, b가 둘 다 음수일 경우는 당연히 합치지 않아야 한다.
그런데 a, b중 하나만 음수일 경우는 n과 m의 크기에 따라서 부호 여부가 달라진다.
사실 위 생각을 대회 시간 내에 따로 하지 않아도 괜찮다. 아래와 비슷한 반례를 금방 찾을 수 있기 때문이다.
5
3 4 -1 -4 -5
ans: 9
wrong: 4-1을 포함해서 3, 4, -1 / -4 / -5 이렇게 세 팀으로 만드는 경우가 3,4 / -1 / -4 / -5 의 경우보다 더 큰 점수를 받을 수 있다.
결국 정렬해준 후, 큰 ai부터 점수가 양수인 팀에 집어넣으면서 점수합이 더 큰지 비교해주어 O(N)으로 해결하였다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
ll N, a[MAX], sum, sum2, cnt, ans = -LNF;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
sum2 += a[i];
}
sort(a, a + N, greater<ll>());
for (int i = 0; i < N; i++) {
cnt++;
sum += a[i];
sum2 -= a[i];
ans = max(ans, sum * cnt + sum2);
}
cout << ans << "\n";
}태그: 골드4, 그리디, 정렬
사실 어떻게 보면 쉽고, 증명 없이 proof by ac도 쉽게 가능하기 때문에 Silver 티어를 준 사람도 보였다.
나는 골드3에 투표하긴 했는데... 골드4~골드5 도 괜찮아보인다.
23743. F - 방탈출
mst를 떠올리는 데엔 크게 어렵지 않다.
그런데 문제는 워프만 설치하는 경우가 시간이 더 빠를 수도 있고, 어떤 간선을 설치하느냐에 따라 특정 워프는 아예 설치할 필요가 없어지기도 하므로 구현이 좀 까다로운 문제였다.
일단 간선 설치 없이 워프만으로 걸리는 시간을 답으로 세팅해주자.
그리고 간선을 설치할 경우에는 두 워프 중 더 오랜 시간이 걸리는 워프를 없애주도록 하자.
이를 구현하기 위해 merge 함수를 if (a>b) swap(a,b)에서 if (t[a]>t[b]) swap(a,b) 로 바꿔주었다.
간선을 설치하여 이득을 보는 시간은 cost - max(t[find(n1)], t[find(n2)]) 이다. merge 함수에서 더 오랜 시간이 걸리는 워프는 merge로 인한 삭제효과를 보기 때문에 cost - max(t[n1], t[n2])가 아닌 find함수를 이용해주어야 한다.
만약 간선을 설치하는 경우가 더 비효율적인 경우라면 간선을 설치하지 않도록 하자.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 200011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, M, p[MAX], t[MAX], ans;
vector<pii> v;
int find(int a) {
if (a == p[a])
return a;
return p[a] = find(p[a]);
}
bool merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return false;
if (t[a] > t[b])swap(a, b);
p[b] = a;
return true;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
for (int i = 0; i < M; i++) {
int a, b, cost;
cin >> a >> b >> cost;
v.push_back({ cost, {a,b} });
}
for (int i = 1; i <= N; i++) {
p[i] = i;
cin >> t[i];
ans += t[i];
}
sort(all(v));
int tmp = ans;
for (int i = 0; i < v.size(); i++) {
int n1 = v[i].second.first;
int n2 = v[i].second.second;
int cost = v[i].first - max(t[find(n1)], t[find(n2)]);
if (cost >= 0)continue;
if (find(n1) != find(n2)) {
merge(n1, n2);
tmp += cost;
ans = min(ans, tmp);
}
}
cout << ans << "\n";
}태그: 골드3, mst
개인적으로는 골드2 정도라 생각한다.
여기서부터는 해결하지 못한 문제들이다.
23744. G - 알고리즘 과외
이분탐색과 투포인터, 스위핑을 골고루 섞으려다가 플레인스위핑 작업을 위한 세그먼트트리를 떠올려 열심히 구현했다.
레이팅 순으로 정렬하여, 더 높은 레이팅을 가지고 있는 경우를 기준으로 스위핑 작업을 해주어
더 낮은 레이팅 보유자와 짝을 이룰 수 있으면 update, 짝을 이루지 못하는 경우라면 INF로 update해준다.
예제가 제대로 나와서 마무리 3분 전 쯤 제출했지만 WA.
더 붙잡진 않았다.
나중에 티어를 확인해보니 플레티넘2였고, 솔루션을 확인해보니 내 풀이 자체가 틀린 것 같진 않아서 다음에 한 번 더 도전해볼 생각이다.
23745. H - 내가 몇 등이었지??
시간 없어서 문제를 보지도 못했는데, 나중에 티어를 확인해보니 다이아3이었고, 태그도 반평면 교집합이라는 알 수 없는 태그인 걸 확인해 안보길 잘했다는 생각이 들었다.
꽤나 재밌게 해결했다.
플레티넘 중하위 난이도가 없는게 좀 아쉽긴 했지만, 이정도로도 충분히 난이도가 있었던 셋이라 생각된다.
우리 학교에서 이 문제셋을 푼사람들이 없어서 학교랭킹에도 꽤나 도움됐던 문제들 ㅎㅎ
'PS > My Diary (PS, 대회후기)' 카테고리의 다른 글
| [211231] Good Bye, BOJ 2021! 참여 후기 (0) | 2022.01.01 |
|---|---|
| [211212] SASA Programming Contest 2021 Open Contest 후기 (0) | 2021.12.13 |
| [211106] 우아한테크코스 4기 1차 코딩테스트 후기 및 결과 (11) | 2021.11.06 |
| [211031] 백준에 잔디 기능이 생겼다 + 나의 백준일지 (0) | 2021.10.31 |
| [211030] 2021 아주대학교 프로그래밍 경진대회 APC Open 후기 (0) | 2021.10.30 |