대회 알림이 6개나 올라와 있길래 할 만한 게 뭐가 있을지 찾아보다가 SNUPC OC Div.2 작년 결과를 보니 대회 우승/준우승 컷이 꽤 낮아서 우승/준우승을 목표로 잡고 참가했다.
대회가 끝났는데 아직 프리즈 이후 상황이 안 나와서 2등 아니면 3등인데 높은 확률로 3등이다.
아쉬운 점은 대회에 늦게 들어온 것과 C 코드를 다 짜고 실수 몇 개 고치다가 노트북 배터리가 부족해서 카페에서 집까지 뛰어서 충전기를 가져오느라 제출이 늦어진 점이다. 또, E에서 해서는 안되는 실수를 했던 점이 아쉽다. 양방향이여서 SPFA가 아니라 dfs 한 번으로 체크하고서 다익스트라를 돌리면 되는 거였는데 착각하고 인터넷에 있는 SPFA 코드를 찾아다가 넣고서 두 번이나 틀렸다.
질문은 언제나 환영입니다.
샤틀버스
문제 요약
사실 무슨 얘기인지 잘 이해가 안 된다. 그냥 대충 맞을 것 같은 코드를 넣어서 맞췄다.
문제 풀이
사실 무슨 얘기인지 잘 이해가 안 된다. 그냥 대충 맞을 것 같은 코드를 넣어서 맞췄다.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
int main() {
int x, y;
scanf("%d %d", &x, &y);
if (x > y) {
printf("%d", x+y);
} else printf("%d", y%x);
}SNUPTI
문제 요약
이 문제는 이름에서 알 수 있듯이 MBTI의 확장된 형태를 다룬다.
SNUPTI 형식은 길이와 각 자리에 사용되는 알파벳의 종류로 정할 수 있다.
그리고 SNUPTI의 서로 다른 자리에는 같은 알파벳을 쓸 수 없다. 예를 들어, ENTT 같은 경우는 불가능하다.
주어진 목록이 어떤 SNUPTI의 형식에 대해 모든 가능한 SNUPTI를 사전순으로 나열한 목록인지 판단하라.
만약 그렇다면, 각 자리에 사용되는 알파벳의 종류를 출력하라.
문제 풀이
주어진 목록에서 사용되는 각 자리의 알파벳들을 std::set 등을 이용하여 뽑아낸 뒤, 서로 다른 자리에 사용되는 알파벳이 겹치는 경우가 존재하는지로 한 번 걸러낸다.
다음은 모든 경우를 나열해볼 차례이다. (필자는 가능한 해가 많이 존재할 것을 우려하여 우선 해의 개수를 비교한 뒤 나열했는데, 실제로 가능한 해의 최댓값이 그리 크지 않아서 이 과정은 생략해도 좋을 것 같다.) 이는 재귀적으로 생성하면 된다.
마지막으로, 주어진 목록을 정렬한 뒤 하나씩 비교해보면 된다. 주어진 목록의 길이와 문자열의 최대 길이의 곱이 작으므로 시간 내에 돌아간다.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 28, M = 20003;
int n, m;
string s[M];
set<char> e[N];
vector<string> v;
char sel[N];
void dfs(int i = 0) {
if (i == n) {
string s;
rep(i,0,n-1) s.push_back(sel[i]);
v.push_back(s);
return;
}
for (char x : e[i]) {
sel[i] = x;
dfs(i+1);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
rep(i,1,m) {
cin >> s[i];
rep(j,0,n-1)
e[j].insert(s[i][j]);
}
{
int cnt[26] = {0,};
rep(i,0,n-1) {
for (auto x : e[i]) {
cnt[x-'A']++;
}
}
rep(i,0,25) if (cnt[i] > 1) {
cout << "NO\n";
return 0;
}
}
{
ll x = 1;
rep(i,0,n-1) {
x *= siz(e[i]);
if (x > m) {
cout << "NO\n";
return 0;
}
}
if (x != m) {
cout << "NO\n";
return 0;
}
}
sort(s+1,s+m+1);
dfs();
rep(i,0,m-1) {
if (v[i] != s[i+1]) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
rep(i,0,n-1) {
for (auto x : e[i]) {
cout << x;
}
cout << '\n';
}
}3에 깃든 힘
문제 요약
트리를 크기가 3인 서브트리들로 쪼갤 수 있는지 판단하고, 가능하다면 쪼갠 각 서브트리들의 노드들을 임의의 순서로 출력하면 된다. 각 서브트리들의 순서도 임의로 하면 된다.
문제 풀이
우선, 필자는 이 문제의 superset이 되는 꽤 어려운 문제를 풀어본 경험이 있어서 쉽게 풀 수 있었다.
이 문제는 백준 7915번 Cave이고, 이 블로그에 풀이가 있다.
각 서브트리의 모양이 어떤지를 고민하면 생각이 복잡해지고 풀이는 불명확해진다.
서브트리로 끊어내는 부분들을 고민하면 문제가 단순해진다.
임의의 정점(이 글에서는 1번 정점)을 루트로 잡고 서브트리로 끊어내는 부분들을 찾아보자.
찾았는가?
바로 자신을 루트로 하는 서브트리의 크기가 3의 배수인 정점들이 부모와 연결하는 간선들이다.
따라서 이러한 간선들을 그래프에서 삭제해준 뒤, 모든 컴포넌트들을 돌면서 포함된 세 개의 정점들을 출력해주면 된다.
이 때, 각 정점에 대해 간선의 사용 여부를 담는 bool 형태의 배열을 이용하면 간선을 그래프에서 삭제해주는 과정을 효율적으로 구현할 수 있다.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 4e6;
int n, cnt_root;
vector<int> adj[N];
vector<char> Stop[N];
bool root[N];
int dfs(int i = 0, int s = 1, int e = 0) {
int sub = 1, par = 0;
for (int j = 0; j < siz(adj[s]); ++j) {
int u = adj[s][j];
if (u != e)
sub += dfs(j,u,s);
else par = j;
}
if (sub%3 == 0) {
Stop[e][i] = true;
if (s != 1) Stop[s][par] = true;
cnt_root++;
root[s] = true;
}
return sub;
}
void dfs1(int s, int e = 0) {
printf("%d ", s);
for (int i = 0; i < siz(adj[s]); ++i) {
int u = adj[s][i];
if (u != e) {
if (!Stop[s][i]) {
dfs1(u,s);
}
}
}
}
int main() {
scanf("%d", &n);
rep(i,1,n-1) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
Stop[0].resize(1);
rep(i,1,n) {
Stop[i].resize(siz(adj[i]));
}
dfs();
if (cnt_root != n/3) {
puts("U");
return 0;
}
puts("S");
rep(i,1,n) if (root[i]) {
dfs1(i);
puts("");
}
}이상한 프로그래밍 언어
문제 요약
이상해서 요약하기 싫다.
문제 풀이
연산의 쌍들에 대해 무엇을 선택할 지를 경우에 따라 잘 고려하면 된다.
문제의 난관은 나머지만으로 정확하게 고려할 수 없고, 몫을 함께 단순하게 기록해도 곱하기 연산 때문에 산술 오버플로우를 피할 수 없다는 것이다.
그러니 몫을 잘 사용한다면 난관을 해결할 수 있다.
몫이 충분히 크다면 제한된 횟수 내에서 최대한 많이 빼도 몫이 $0$보다 작아질 수 없다는 점을 이용하자. 즉, 몫이 $N$보다 크다면 모든 연산이 $-10^9$이더라도 몫이 $0$보다 크다.
그러면 몫이 충분히 커졌을 때 더 이상 몫에 값을 곱하지 않게 하여 산술 오버플로우를 피할 수 있다.
다른 경우에 대해서는 단순하게 고려할 수 있으므로 서술하지 않겠다. 다만, 경우가 워낙 많으므로 뭔가 빼먹어 틀리기 쉽다는 점을 유의하라.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 3e5+3, K = 1e9+3, MOD = 1e9+7;
int n;
struct Num {
ll a, b;
void operator += (int x) {
if (a < MOD) a += (b+x)/MOD;
b = (b+x)%MOD;
}
void operator -= (int x) {
if (b >= x) {
b -= x;
} else {
if ((b-x)%MOD == 0) {
if (a < MOD) a += (b-x)/MOD;
b = 0;
if (a < 0) a = 0;
if (a == 0 && b < 0) a = b = 0;
} else {
if (a < MOD) a += (b-x)/MOD-1;
b = MOD+(b-x)%MOD;
if (a < 0) a = b = 0;
if (a == 0 && b < 0) a = b = 0;
}
}
}
void operator *= (int x) {
if (x == 0) a = b = 0;
else {
if (a < MOD) a = (b*x)/MOD;
b = (b*x)%MOD;
}
}
} k;
int main() {
int k0;
scanf("%d %d", &n, &k0);
k = {0,k0};
rep(i,1,n) {
char c, d; int x, y;
scanf(" %c%d ", &c, &x);
scanf(" %c%d ", &d, &y);
if (c == '+') {
if (d == '+')
k += max(x,y);
if (d == '-')
k += x;
if (d == '*') {
if (y <= 1) k += x;
else {
if (k.a >= 1) {
k *= y;
} else {
if (k.b*y > k.b+x) {
k *= y;
} else {
k += x;
}
}
}
}
}
if (c == '-') {
if (d == '+')
k += y;
if (d == '-')
k -= min(x,y);
if (d == '*') {
if (y == 0) k -= x;
else k *= y;
}
}
if (c == '*') {
if (d == '+') {
if (x <= 1) k += y;
else {
if (k.a >= 1) {
k *= x;
} else {
if (k.b*x > k.b+y) {
k *= x;
} else {
k += y;
}
}
}
}
if (d == '-') {
if (x == 0) k -= y;
else k *= x;
}
if (d == '*')
k *= max(x,y);
}
// cerr << k.a << ' ' << k.b << '\n';
}
printf("%lld", k.b);
}자취방 정하기
문제 요약
각 간선은 각각 50%의 확률로 가중치가 $a$이거나 $b$인 양방향 그래프가 있다.
1번 정점과의 최단 경로의 기댓값이 $T$ 이하인 정점들을 모두 출력하라. 단, $a, b, t$는 음수일 수 있다.
문제 풀이
기댓값은 선형성이 있다. 즉, $E[w_1+w_2]=E[w_1]+E[w_2]$이다.
그러므로 각 간선의 기댓값을 간선의 가중치처럼 다룬 뒤 최단 경로를 구하여도 문제가 없다.
따라서 후술할 모든 내용은 간선의 가중치를 간선의 기댓값으로 바꿔 적을 것이다.
양방향 그래프이기 때문에 간선의 가중치가 음수라면 음의 사이클이 존재하는 꼴이다.
따라서 정점 1과 연결된 컴포넌트 내부에 가중치가 음수인 간선이 존재하는지 확인하고, 존재한다면 정점 1을 제외한 컴포넌트 내의 모든 정점들을 출력한다.
존재하지 않는다면 다익스트라 알고리즘을 이용해 단순히 최단 경로를 구할 수 있다.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 2e5+3;
const ll INF = 1e18;
int n, m;
vector<pair<int,ll>> adj[N];
ll dist[N], t;
bool vis[N];
bool has_negative(int s = 1) {
if (vis[s]) return false;
vis[s] = true;
for (auto [u,w] : adj[s]) {
if (w < 0) return true;
if (has_negative(u)) return true;
}
return false;
}
int main() {
scanf("%d %d", &n, &m);
rep(i,1,m) {
int u, v, a, b;
scanf("%d %d %d %d", &u, &v, &a, &b);
adj[u].push_back({v,a+b});
adj[v].push_back({u,a+b});
}
scanf("%lld", &t);
t *= 2;
if (has_negative()) {
printf("%d\n",n-1);
rep(i,2,n) printf("%d ", i);
return 0;
}
priority_queue<pair<ll,int>> pq;
pq.push({0,1});
fill(dist+2,dist+N,INF);
while (not empty(pq)) {
auto [d,a] = pq.top(); pq.pop(); d = -d;
if (d != dist[a]) continue;
for (auto [b,w] : adj[a]) {
if (dist[b] > d+w) {
dist[b] = d+w;
pq.push({-d-w,b});
}
}
}
// rep(i,1,n) fprintf(stderr,"%lld ", dist[i]);
vector<int> v;
rep(i,2,n) {
if (dist[i] <= t) {
v.push_back(i);
}
}
printf("%d\n",siz(v));
for (auto e : v) {
printf("%d ", e);
}
}콜라 줍기(풀이 준비중...)
문제 요약
$N\times N$ 격자 내에서 $(1,1)$에서 $(N,N)$를 잇는 겹치지 않는 두 경로(이 두 정점은 예외로 한다)에 대해 가중치의 합을 최대화하라.
이 때 두 경로는 각각 격자에 배정된 가중치가 다르다. 하나는 $c_{i,j}$를 가중치로 가지고, 다른 하나는 $p_{i,j}$를 가중치로 가진다.
슬라임 키우기
문제 요약
지문의 길이가 충분히 짧으므로 적지 않겠다.
문제 풀이
$y_i=0$일 경우, $x_i$ 이하의 모든 슬라임을 $0$으로 바꾸면 된다. $0$으로 만든 슬라임은 앞으로도 $0$일 것이 분명하므로 고려 대상에서 제외하고, zero_count 따위의 변수를 이용해 개수만 세주자.
$y_i=1$일 경우, 아무런 영향이 없으므로 건너뛰어도 좋다.
$y_i\ge 2$일 경우, $x_i\le 10^9$이라는 조건을 생각하면 최대 $30$번 이내밖에 곱할 수 없다. 따라서 이 경우는 상대적으로 Naive하게 계산해도 좋다.
이 과정들을 heap을 이용하여 잘 구현하면 된다.
정답 코드
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const int N = 2e5+3, Q = N;
int n, q;
priority_queue<ll,vector<ll>,greater<>> pq;
int zero_count;
int main() {
scanf("%d %d", &n, &q);
rep(i,1,n) {
int a; scanf("%d", &a);
pq.push(a);
}
rep(_,1,q) {
ll x, y;
scanf("%lld %lld", &x, &y);
if (y == 0) {
while (not empty(pq) and pq.top() <= x)
zero_count++, pq.pop();
} else if (y > 1) {
vector<ll> tmp;
while (not empty(pq) and pq.top() <= x) {
tmp.push_back(pq.top() * y);
pq.pop();
}
for (auto e : tmp) pq.push(e);
}
}
rep(i,1,zero_count) printf("0 ");
while (not empty(pq)) {
printf("%lld ", pq.top());
pq.pop();
}
}포켓몬 대회(풀이 준비중...)
문제 요약
'PS 기록들' 카테고리의 다른 글
| 2023 KAKAO BLIND RECRUITMENT 해설 (2) | 2022.09.24 |
|---|---|
| 2022.09.20 PS 일지 (BOJ 19679) (0) | 2022.09.20 |
| 2022.09.12 PS 일지 (0) | 2022.09.12 |
| AtCoder Regular Contest 147 ★ (0) | 2022.09.05 |
| NYPC 2022 Round 2-B 후기 (0) | 2022.09.04 |
