Codeforces Global Round 21 1684 → 1665
https://codeforces.com/contest/1696
Dashboard - Codeforces Global Round 21 - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!
A. NIT orz!
https://codeforces.com/contest/1696/problem/A
Problem - A - Codeforces
codeforces.com
문제
- 한개의 원소를 골라서 a[i] = (a[i] | z) , z = (a[i] & z) 로 set 한다.
풀이
z는 and 연산을 시킬 수록 값이 작아지니 최대 한번을 or 시킬 원소를 모두 비교해보고 최대 값을 출력해준다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[2001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
long long n, z;
cin >> n>>z;
long long ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ans = max(ans, (a[i] | z));
}
cout << ans << '\n';
}
}
B. NIT Destroys the Universe
https://codeforces.com/contest/1696/problem/B
Problem - B - Codeforces
codeforces.com
문제
n길이의 배열 a가 주어진다 . 아래의 operation을 원하는 만큼 할 수 있을 때 모든 원소를 0으로 만들 기 위한 최소 operation의 수를 출력하는 문제
- l과 r을 골라 그 사이에 해당하는 인덱스를 mex(a[l]...a[r])의 값으로 바꾼다.
풀이
최대 opertaion의 수는 2개이다. 0이 아닌 덩어리의 개수를 세주고 둘중 작은값을 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[100001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i]) {
int i2 = i + 1;
while (i2 < n) {
if (a[i2])i2++;
else break;
}
i = i2 - 1;
ans++;
}
}
cout << min(ans,2) << '\n';
}
}C. Fishingprince Plays With Array
https://codeforces.com/contest/1696/problem/C
Problem - C - Codeforces
codeforces.com
문제
n길이의 배열 a와 k길이의 배열 b와 m이 주어진다. 2개의 operation이 있고 한번의 1개의 opertion을 골라 a에 원하는 만큼 수행할 수 있을 때 a배열을 b와 똑같이 만들 수 있다면 Yes를 아니라면 No를 출력하는 문제
- m으로 나뉘는 a[i]를 골라서 m개의 a[i]/m 으로 분해한다
- m개의 연속된 같은 숫자가 있다면 m개의 원소를 a[i]*m으로 합친다.
풀이
b를 분해하는 opertion도 순서가 변하지 않기 때문에 사실상 가능하다. 둘중 큰 원소를 쪼개주면서 하는 방향으로 계산해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[50001];
long long b[50001];
stack<pair<long long,long long>> ast, bst;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
while (!ast.empty())ast.pop();
while (!bst.empty())bst.pop();
long long n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)cin >> a[i];
long long k;
cin >> k;
for (int i = 0; i < k; i++)cin >> b[i];
bool flag = true;
for (int i = n - 1; i >= 0; i--)ast.push({ a[i],1 });
for (int i = k - 1; i >= 0; i--)bst.push({ b[i],1 });
while (!ast.empty() && !bst.empty()) {
long long a = ast.top().first, b = bst.top().first;
long long as = ast.top().second, bs = bst.top().second;
//cout << a << ' ' << b << '\n';
if (a == b) {
ast.pop(); bst.pop();
long long MIN = min(as, bs);
as -= MIN; bs -= MIN;
if (as != 0)ast.push({ a,as });
if (bs != 0)bst.push({ b,bs });
}
else if (a > b) {
ast.pop();
if (as != 1)ast.push({ a,as - 1 });
long long a2 = a;
bool tflag = false;
while (a2 % m == 0) {
a2 /= m;
if (a2 == b) {
tflag = true;
}
if (a2 <= b)break;
}
if (tflag == false) {
flag = false;
break;
}
a2 = a;
while (a2 % m == 0) {
a2 /= m;
ast.push({ a2,m - 1 });
if (a2 == b)break;
}
bst.pop();
if (bs != 1)bst.push({ b,bs - 1 });
}
else {
bst.pop();
if (bs != 1)bst.push({ b,bs - 1 });
long long b2 = b;
bool tflag = false;
while (b2 % m == 0) {
b2 /= m;
if (b2 == a) {
tflag = true;
}
if (b2 <= a)break;
}
if (tflag == false) {
flag = false;
break;
}
b2 = b;
while (b2 % m == 0) {
b2 /= m;
bst.push({ b2,m - 1 });
if (b2 == a)break;
}
ast.pop();
if (as != 1)ast.push({ a,as - 1 });
}
}
if (ast.size() || bst.size())flag = false;
if (flag)cout << "Yes\n";
else cout << "No\n";
}
}
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.