2021. 01. 05 23:35 본 라운드 참가
실력이 정체되어있다.
예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다....
재활이 꽤 오래 걸릴 것 같다.
1471A. Strange Partition
주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다.
이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다.
최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
ll n, x; cin >> n >> x;
ll mi = 0, mx = 0;
for (int i = 1; i <= n; i++) {
ll a; cin >> a;
mi += a;
mx += (a + x - 1) / x;
}
cout << (mi + x - 1) / x << ' ' << mx << '\n';
}
}
1471B. Strange List
배열의 원소를 앞에서부터 차례대로 보면서, x로 나누어 떨어지면 배열의 끝에 A[i]/x를 x개만큼 추가해준다.
그리고 추가한 원소들에 대해서도 같은 방식으로 진행해나간다.
만약 x로 나누어 떨어지지 않으면 작업을 종료하고 배열의 모든 원소의 합을 구한다.
먼저, x로 나누어 떨어질 때 배열에 추가되는 원소의 합은 원래 배열의 원소와 동일한 것을 알 수 있다.
그리고 언제 처음 x로 나누어 떨어지지 않는 수가 나오는지를 체크한다.
x로 나누어 떨어지지 않을 때까지 나눌 수 있는 횟수가 가장 작은 원소의 인덱스를 k라고 하고,
A[k]의 나눌 수 있는 횟수를 cnt라고 하면 A[1] ~ A[k-1] 까지는 cnt+1번 나눌 수 있고, A[k] ~ A[n] 까지는 cnt번 나눌 수 있다.
A[k]를 cnt번 나누게 되면 x로 더 이상 나누어 떨어지지 않게 되고, 따라서 수행이 종료되기 때문이다.
따라서 A[1] ~ A[n]의 합을 cnt번 더하고, A[1] ~ A[k-1]의 합을 더 더해주면 된다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int A[100001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
ll n, x; cin >> n >> x;
ll sum = 0;
ll cnt = 1000;
ll k;
for (int i = 1; i <= n; i++) {
cin >> A[i];
sum += A[i];
ll a = A[i];
ll c = 0;
while (1) {
if (a%x == 0) {
a /= x;
c++;
}
else {
if (cnt > c) {
cnt = c;
k = i;
}
break;
}
}
}
ll ans = sum*(cnt + 1);
for (int i = 1; i < k; i++) {
ans += A[i];
}
cout << ans << '\n';
}
}
1471C. Strange Birthday Party
각 친구들은 번호 $k_i$를 가지고 있고, 상점에 선물들의 가격이 오름차순으로 나열되어있고 1부터 m까지 차례대로 번호가 부여되어있다.
선물들은 종류별로 1개씩만 살 수 있으며, 친구들에게 해당 친구의 번호보다 작거나 같은 선물을 구매하여 주거나 혹은 $k_i$ 번째 선물의 가격만큼 돈을 준다.
친구들에게 드는 비용의 합을 최소화 시키는 문제이다.
먼저 친구들의 번호를 오름차순으로 정렬한다.
상품의 가격들이 오름차순으로 주어지기 때문에 돈으로 지불한다면 친구의 번호가 클수록 비용이 많이 든다.
그러므로 번호가 큰 친구들부터 차례대로 싼 상품들을 선물하는 게 최적이다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll k[300001];
ll c[300001];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
ll n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> k[i];
for (int i = 1; i <= m; i++) cin >> c[i];
sort(k + 1, k + n + 1);
ll left = 1;
ll ans = 0;
for (int i = n; i >= 1; i--) {
if (left > k[i]) ans += c[k[i]];
else ans += c[left++];
}
cout << ans << '\n';
}
}
1471D. Strange Definition
두 수 $x$와 $y$가 'adjacent' 하다는 의미는 $lcm(x, y) / gcd(x, y)$가 완전 제곱수인 경우이다.
$lcm(x, y) = x*y / gcd(x, y)$ 이므로 $lcm(x, y) / gcd(x, y) = x*y / gcd(x, y)^2 $ 가 완전 제곱수가 되어야 한다.
따라서 결국 $x*y$가 완전제곱수가 되어야 한다.
$x$와 $y$를 각각 소인수분해 했을 때 $x*y$가 완전 제곱수가 되기 위해서는 소인수의 지수가 모두 짝수이어야 한다.
따라서 'adjacent' 의 여부를 판단하기 위해서는 지수의 홀, 짝만 중요하기 때문에 소인수분해를 하고, 지수에 mod 2를 취해준다.
예를 들면 $108 = 2^2*3^3 = 3$ 과 같이 바꿔서 생각해도 무방하다.
그러면 이제, $x$와 $y$가 adjacent한 경우는 $x$와 $y$가 같은 경우이다.
같은 원소가 짝수개 있다면 한번 연산을 수행하면 그 원소들의 곱의 지수가 모두 짝수가 되므로 1이 된다.
만약 홀수개 있다면 곱해도 지수는 여전히 홀수이므로 값이 변하지 않는다.
따라서 한번의 연산으로 배열의 원소가 1이 되거나 혹은 그대로 유지되기 때문에 w = 0 인 경우와 w > 0인 경우, 두 경우만 생각해주면 된다.
[소스 코드]
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int prime[1000001];
int A[300001];
int tosmall(int a) {
int res = 1;
int cnt = 0;
int last = prime[a];
while (a > 1) {
if (last == prime[a]) {
cnt++;
a /= prime[a];
}
else {
if (cnt % 2) res *= last;
last = prime[a];
cnt = 0;
}
}
if (cnt % 2) res *= last;
return res;
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
for (int i = 1; i <= 1000000; i++) prime[i] = i;
for (int i = 2; i <= 1000000; i++) {
if (prime[i] == i) {
for (int j = 2; j*i <= 1000000; j++) {
prime[i*j] = i;
}
}
}
int T; cin >> T;
while (T--) {
int n; cin >> n;
map<int, int>mp;
for (int i = 1; i <= n; i++) {
cin >> A[i];
A[i] = tosmall(A[i]);
mp[A[i]]++;
}
int ans1 = 1;
int ans2 = 0;
for (auto it = mp.begin(); it != mp.end(); it++) {
ans1 = max(ans1, it->second);
if (it->second % 2 == 0 || it->first == 1) ans2 += it->second;
}
int q; cin >> q;
for (int i = 1; i <= q; i++) {
ll w; cin >> w;
if (w == 0LL) cout << ans1 << '\n';
else cout << max(ans1, ans2) << '\n';
}
}
}
1471E. Strange Shuffle
어렵다... 해설만 대충 읽어봤고 코드 구현은 하지 않았다.
대충 이런식이다~ 정도만 적어두었기 때문에 정확한 풀이를 원한다면 공식 해설을 참고하면 될 것 같다.
먼저, 매 연산마다 p를 기준으로 양쪽에 값이 변하는 사람이 한 명씩 늘어난다.
제일 안쪽이 초기상태이고 연산을 한 번씩 할 때마다 바깥쪽으로 변해간다.
빨간 원이 p라고 한다면, 이처럼 p를 기준으로 연산을 할 때마다 한쪽은 k보다 큰 수가 증가하고, 한쪽은 k보다 작은 수가 증가한다.
따라서, n명을 연속된 $\sqrt{n}$명의 사람들로 각 구간을 잘 나누면 연산을 $\sqrt{n}$번 수행했을 때 k보다 큰 수들로 이루어지는 구간이 정확히 하나 만들어질 것이다.
그러면 그 구간의 가장 왼쪽 사람의 왼쪽에 p가 존재할 것이다.
1471F. Strange Housing
다음 세 조건을 만족하면서 선생님이 있을 정점을 고를 수 있으면 YES, 아니면 NO이다.
조건 1. 간선을 이루는 두 정점에 모두 선생님이 없다면, 해당 간선은 이용할 수 없다.
조건 2. 이용가능한 간선을 통해서 임의의 두 집 사이를 항상 이동할 수 있다.
조건 3. 선생님이 있는 두 정점은 이웃할 수 없다.
먼저, NO인 경우는 주어진 그래프가 연결 그래프가 아닌 경우이다. 연결그래프가 아니라면 항상 두 번째 조건을 만족시킬 수 없기 때문이다.
반대로 그래프가 연결그래프이면 항상 YES이다.
각 정점을 선생님이 있는 정점과 없는 정점으로 구분되므로 흑백으로 칠해준다고 생각하자. (검은색 == 선생님 O)
임의의 정점을 하나 잡아서 검은색으로 칠해주고 이 정점을 루트로 하는 BFS 트리를 만들어간다.
현재 정점에 색을 칠할 때, 인접한 모든 정점들 중 하나라도 검은색이 있다면 흰색을 칠해준다.
만약 인접한 모든 정점이 흰색이라면 현재 정점에 검은색을 칠해준다.
이 방식이 항상 문제의 모든 조건을 만족할 수 있을까?
우선 검은색 정점과 이웃한 정점들은 모두 흰색을 칠할 수밖에 없으므로 조건 3에 위배되지 않는다.
또 흰색 정점은 이웃한 정점 중 적어도 하나는 검은색이기 때문에 흰색이 칠해졌으므로 마찬가지로 조건 3에 위배되지 않는다.
그리고 두 집을 연결하는 모든 간선들은 항상 서로 다른 색이 칠해진 정점으로 연결되어있으므로 조건 2를 만족시킨다.
[소스 코드]
#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) {
int n, m; cin >> n >> m;
vector<vector<int>>adj(n + 1, vector<int>());
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> chk(n + 1);
chk[1] = 1;
queue<int> q;
q.push(1);
while (!q.empty()) {
int now = q.front(); q.pop();
for (int next : adj[now]) {
if (chk[next] != 0) continue;
bool a = false;
for (int i : adj[next]) {
if (chk[i] == 1) a = true;
}
chk[next] = a ? -1 : 1;
q.push(next);
}
}
bool flag = true;
vector<int> ans;
for (int i = 1; i <= n; i++) {
if (chk[i] == 0) flag = false;
else if (chk[i] == 1) ans.push_back(i);
}
if (!flag) cout << "NO\n";
else {
cout << "YES\n" << sz(ans)<<'\n';
for (int i : ans) cout << i << ' ';
cout << '\n';
}
}
}
'프로그래밍 대회 풀이 > Codeforces' 카테고리의 다른 글
| [Codeforces] Educational Round 102 A ~ E 풀이 (0) | 2021.01.20 |
|---|---|
| [Codeforces] Round #552 (Div. 3) A ~ E 풀이 (0) | 2021.01.11 |
| [Codeforces] Round #551 (Div. 2) A ~ D 풀이 (2) | 2021.01.04 |
| [Codeforces] Educational Round 76 (A ~ E) 풀이 (2) | 2021.01.03 |
| Codeforces Round #690 (Div. 3) 풀이 (0) | 2020.12.16 |
