2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844)
테크노컵은 뭔가 항상 어려운 느낌이다...
생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다.
A. Prison Break (*800)
모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다.
답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다.
정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자.
벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상의 칸이 한번에 상태가 바뀔 수 있는지를 생각해보면 이런 경우가 존재하지 않음을 알 수 있다.
따라서 한 번의 벽 제거로는 칸의 개수를 최대 1개 줄이거나 최대 한 칸을 밖으로 더 내보낼 수 있다.
그러므로 답은 칸의 개수가 된다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
int a, b; cin >> a >> b;
cout << a*b << '\n';
}
}
B. Restore Modulo (*1500)
n개의 원소로 이루어진 배열이 주어질 때, a[1] = s이고, i>1일 땐 a[i] = (a[i-1] + c)%m 을 만족하는 m, c, s가 존재하는지를 구하는 문제이다.
존재한다면 가능한 m중 가장 큰 경우를 구하고, m이 무한히 클 수 있다면 0을 출력한다.
기본적으로 c가 0이상이므로 원소가 감소하는 부분이 생긴다면 m에 영향을 받았다는 의미이다.
우선 m이 무한히 클 수 있는 경우는 어떤 경우일까?
m이 배열에 영향을 주지 않는 경우이며, 이는 입력된 배열이 등차수열이라면 가능하다.
1) 배열의 원소가 모두 동일
s = a[1], c = 0인 경우이고 따라서 m > s이기만 하면 된다.
2) 배열이 단조증가하는 등차수열
m보다 커지는 경우가 없다는 의미이고, 결국 m > a[n]이기만 하면 된다.
3) 배열이 단조감소하는 등차수열
예를 들어 a[1], a[1] - k, a[1] - 2k, .... , a[1] - (n-1)k 로 주어진다면, c = m - k만 만족하면 된다.
따라서 m이 무한히 커지더라도 만족하는 c값인 m-k가 존재하므로 가능하다.
불가능한 경우는 어떤 경우일까?
일단 이전에 고려한 단조증가하거나 단조감소하는 경우를 제외하면 반드시 a[i] > a[i-1]인 부분이 하나는 존재한다.
c < m이기 때문에 만약 증가했다면 이 부분은 c만큼 더해졌다는 의미이다.
그러므로 반드시 c = a[i] - a[i-1]이 되어야 한다.
따라서 만약 a[i] - a[i-1] ≥ 0인 i중에서 a[i] - a[i-1]의 값이 다른 i가 존재한다면 이를 만족하는 c가 존재하지 않게 된다.
이 경우는 불가능하다.
이를 제외하면 이제 c는 고정이 되었고, 최대의 m을 찾아주어야 한다. 최대의 m은 a[i] > a[i+1]인 i중에서 a[i]가 가장 큰 부분을 골라서 적절하게 m을 만들어주면 된다. (a[i] + c) %m = a[i+1] 이므로 m = a[i] - a[i+1] + c를 만족한다.
최종적으로, 선택된 m에 대해서 a[i] < a[i-1]인 부분에 대해서 조건을 만족하는지 체크해주면 된다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
bool ismono = true;
for (int i = 2; i < n; i++) {
if (a[i] - a[i - 1] != a[i + 1] - a[i]) ismono = false;
}
if (n == 2 || ismono) {
cout << 0 << '\n';
continue;
}
bool chk = true;
int c = -1;
int m = -1;
for (int i = 2; i <= n; i++) {
if (a[i] >= a[i - 1]) {
if (c == -1) c = a[i] - a[i - 1];
else if(c != a[i] - a[i-1]) chk = false;
}
}
for (int i = 2; i <= n; i++) {
if (a[i] < a[i - 1]) {
m = max(m, c - a[i] + a[i - 1]);
}
}
if (a[1] >= m) chk = false;
if (!chk) {
cout << -1 << '\n';
continue;
}
for (int i = 2; i <= n; i++) {
if (a[i] != (a[i - 1] + c) % m) chk = false;
}
if (!chk) cout << -1 << '\n';
else cout << m << ' ' << c << '\n';
}
}
C. Basic Diplomacy (*1600)
간단하게 요약해서, 원소 m개의 배열을 1~n 범위의 숫자들로 채우는데 각 위치마다 가능한 숫자의 후보들이 주어지고, (m+1)/2번 넘게 사용되는 숫자가 존재하면 안된다.
그리디로 해결할 수 있는데, 정확한 증명이 어려워 증명은 생략하겠다.
* 호프크로프트(이분매칭) 알고리즘으로 오버킬이 가능하다고 한다. 대회중에 플로우도 생각했는데 div2 C인 것도 있고 시간복잡도를 잘못 생각한 부분도 있어서 무시했다.
후보의 수가 적은 순서대로 숫자를 채워나가고, 숫자를 채울 때에는 아직 (m+1)/2개를 사용하지 않은 수 중 가장 후보로 많이 존재하는 숫자를 이용한다.
[소스 코드]
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using pii = pair<int, int>;
vector<int> team[100010]; //team[i] = i번째의 후보들
int cnt[100010]; //i를 사용할 수 있는 남은 횟수
int used[100010]; //used[i] = 숫자 i를 사용한 횟수
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
int T; cin >> T;
while (T--) {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
cnt[i] = 0;
used[i] = 0;
}
vector<pii> round;
for (int i = 1; i <= m; i++) team[i].clear();
for (int i = 1; i <= m; i++) {
int k; cin >> k;
for (int j = 1; j <= k; j++) {
int a; cin >> a;
team[i].push_back(a);
cnt[a]++;
}
round.push_back({ k, i });
}
sort(all(round));
bool chk = true;
vector<int> ans(m + 1);
for (auto[a, i] : round) { //i번째 라운드
int mx = 0;
int idx = -1;
for (int a : team[i]) {
if (cnt[a] > 0 && used[a] < (m + 1) / 2) {
if (mx < cnt[a]) {
mx = cnt[a];
idx = a;
}
}
}
if (idx == -1) {
chk = false;
break;
}
ans[i] = idx;
cnt[idx]--;
used[idx]++;
}
if (!chk) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= m; i++) cout << ans[i] << ' ';
cout << '\n';
}
}
}
에디토리얼의 풀이가 훨씬 간단하다.
임의로 숫자들을 배정하고나면 (m+1)/2보다 많이 배정된 숫자를 a라고 하면 a는 최대 1개밖에 존재하지 않다는 게 자명하다.
따라서 a가 배정된 횟수가 (m+1)/2가 되도록, a가 배정된 위치들에서 다른 후보가 존재하면 다른 후보로 바꿔주면 된다.
이게 불가능하다면 "NO"를 출력하면 된다.
코드상에서는 임의로 숫자를 배정하는 것을 단순하게 첫번째 입력된 숫자로 배정하였다.
[소스 코드]
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
vector<int> v[100001];
int cnt[100001];
int n, m, mxnum, k;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
cin >> n >> m;
int mx = 0;
for (int i = 1; i <= n; i++) cnt[i] = 0;
for (int i = 1; i <= m; i++) v[i].clear();
for (int i = 1; i <= m; i++) {
cin >> k;
while (k--) {
int a; cin >> a;
v[i].push_back(a);
}
cnt[v[i][0]]++;
if (mx < cnt[v[i][0]]) {
mx = cnt[v[i][0]];
mxnum = v[i][0];
}
}
if (mx > (m + 1) / 2) {
for (int i = 1; i <= m; i++) {
if (mxnum == v[i][0]) {
if (sz(v[i]) > 1) {
swap(v[i][0], v[i][1]);
mx--;
}
if (mx <= (m + 1) / 2) break;
}
}
}
if (mx > (m + 1) / 2) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= m; i++) cout << v[i][0] << ' ';
cout << '\n';
}
}
}
D. Playlist (*?)
n개의 원소로 이루어진 배열이 주어지고, 1->2->...->n->1->2... 와 같이 계속 배열을 탐색한다.
a[i]차례가 되었을 때, gcd(a[i], a[i+1]) = 1이면 a[i+1]을 지우고 a[i+2]부터 다시 탐색하기 시작한다.
이때, 지워진 자리는 비워두지 않고 뒤의 원소들을 한칸씩 앞으로 당긴다. 더이상 지울 수 있는 쌍이 없을 때 종료한다.
예를 들어 예시로 [5, 9, 2, 10, 15]가 주어진다면 다음과 같이 진행된다.
[5, 9, 2, 10, 15] -> [5, 9, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 2, 10, 15] -> [5, 10, 15] END
최종적으로, 지워지는 원소들을 구하는 것이 문제이다.
먼저, 각 원소들은 최대 1번 지워지므로 지울 수 있는 쌍들을 차례대로 고려해도 시간적으로 문제가 되지 않는다.
다만 원소가 지워짐으로 인해서 뒤의 원소들이 한칸씩 앞으로 당겨지는데 이를 naive하게 구현하면 한번 당길때마다 O(n)의 시간이 소모가 된다.
따라서 현재 원소의 다음 원소를 더 빠르게 찾을 수 있어야 한다. 이를 set (alive)으로 관리한다.
alive에 index 번호를 모두 넣어두고, 지워지는 원소들의 index들은 제거하면서 현재 원소의 다음 원소 index는 set.lower_bound 함수로 O(logn)만에 구할 수 있다.
그다음 지워야 하는 쌍들을 또다른 set (die)에 저장해둔다.
현재 A[a] 다음에 A[b]가 있다고 하고, gcd(A[a] , A[b]) = 1이라고 가정하다. 그러면 A[b]는 지워져야 한다.
A[b]의 다음 원소를 A[c]라고 하고, gcd(A[b], A[c]) = 1이라면 die에는 {A[b], A[c]}가 포함되어있을 것이다.
하지만 A[b]가 지워짐에 따라서 A[b]에 의해서는 A[c]는 지워지지 않는다. 이를 die에서 제거해준다.
A[b]를 제거하고 나면 A[a]의 다음 원소는 A[c]가 된다. 만약 gcd(A[a], A[c]) = 1이라면 지워야하는 쌍이 새로 추가되는 것이므로 die에 {A[a], A[c]} 를 넣어준다.
최종적으로 die의 원소들이 모두 제거될 때까지 수행을 반복해주면 결과를 얻을 수 있다.
[소스 코드]
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
using pii = pair<int, int>;
int a[100001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
int n; cin >> n;
set<int> alive;
set<pii> die;
for (int i = 1; i <= n; i++) cin >> a[i], alive.insert(i);
alive.insert(n + 1);
for (int i = 1; i < n; i++) {
if (gcd(a[i], a[i + 1]) == 1) die.insert({ i, i + 1 });
}
if (gcd(a[n], a[1]) == 1) die.insert({ n , 1 });
vector<int> ans;
while (!die.empty()) {
set<pii> tmp;
for (auto[i, j] : die) {
if (alive.find(i) == alive.end() || alive.find(j) == alive.end()) continue;
int k = *alive.lower_bound(j+1);
if (k == n + 1) k = *alive.begin();
//i -> j -> k & erase j
alive.erase(j);
ans.push_back(j);
if (die.find({ j, k }) != die.end()) die.erase({ j, k });
if (tmp.find({ j, k }) != tmp.end()) tmp.erase({ j, k });
if (i != j && gcd(a[i], a[k]) == 1) tmp.insert({ i, k });
if (die.empty()) break;
}
die = tmp;
}
cout << sz(ans) << ' ';
for (int i : ans) cout << i << ' ';
cout << '\n';
}
}
PC로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^
'프로그래밍 대회 풀이 > Codeforces' 카테고리의 다른 글
| [Codeforces] Round #706 (Div. 2) A ~ D 풀이 (0) | 2021.03.12 |
|---|---|
| [Codeforces] Round #705 (Div. 2) A ~ D 풀이 (0) | 2021.03.08 |
| [Codeforces] Round #559 (Div. 2) A ~ E 풀이 (0) | 2021.03.07 |
| [Codeforces] Educational Round 102 A ~ E 풀이 (0) | 2021.01.20 |
| [Codeforces] Round #552 (Div. 3) A ~ E 풀이 (0) | 2021.01.11 |
