#651 후기
Div2의 D번의 벽을 크게 체감한 대회였다. 대회 이후 문제 레이팅을 확인해봤는데 무려 2000점인걸 보고 확실히 차근차근 실력을 키우지 않으면 우연히라도 높은 난이도의 문제를 풀지 못할거라고 생각이 들었다. 그래도 다행인건, A ~ C번과 같은 비교적 쉬운 난이도의 문제는 어떻게든 풀 수 있게 실력이 조금은 오른것 같다고 느꼈다.
#651 문제
A번 Maximum GCD - 성공
정수 N이 주어진다. 1 <= a < b <= N인 두 정수 a, b에 대해서, gcd(a, b)의 최댓값을 출력하시오.
gcd(a, b)에서 될 수 있는 가장 큰 값은 a 이다.
왜냐하면 약수 중 가장 큰 값은 자기자신이고, a < b 이므로, a를 초과한 공약수는 존재할 수 없다.
따라서 a가 가장 큰 경우가 정답이고, 이는 a == N/2일때이다.
아래는 제출코드이다.
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
// 전역변수
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int tc;
cin >> tc;
while(tc--) {
int a;
cin >> a;
cout << a/2 << "\n";
}
return 0;
}B번 GCD Compression - 성공
길이가 2n인 정수 배열 a가 있다. 배열 a에서 원소 두 개를 선택하여 합한 값을 배열 b에 추가할 수 있다. 이때, 배열 b는 다음과 같은 조건을 만족해야 한다. 모든 원소의 최대공약수(GCD)가 1보다 커야하고, 배열 b의 길이는 (n - 1)이다. 조건을 만족하는 배열 b를 만들기 위해 선택한 Index쌍을 모두 출력하시오.
문제의 조건을 다시 한번 확인하면,
1. 배열 b의 모든 원소의 GCD가 1 초과이다.
2. 배열 b의 길이는 (n - 1)이다.
의 두가지이다.
첫번째 조건에서 모든 원소가 짝수이면, 모든 원소의 GCD는 최소 2이므로, 1보다 클 수 있겠다고 생각하였다. (그리디)
그래서, 배열 a에서 두 원소를 뽑아서 합한 값을 배열 b의 원소로 추가하므로, 배열 a에서 (n - 1)개의 짝수를 만들 수 있는지를 확인하면 되겠다고 생각했다.
두 값을 합쳤을 때 짝수이려면, (홀수 + 홀수) 또는 (짝수 + 짝수) 두 경우뿐이다.
만약 배열 b의 길이가 n이였다면 불가능한 경우가 있었을 수도 있겠지만, 배열의 길이가 (n - 1)이므로, 내가 확인했을 때는 어느 경우에서나 가능했었다.
따라서 경우에 맞춰서
1. 홀수끼리 또는 짝수끼리만 있는 경우 - 앞에서부터 (2i, 2i + 1) (i = 0, 1, 2, ...)쌍을 (n - 1)개 출력
2. 그 외 - 짝수의 Index쌍을 먼저 출력하고, 이후 홀수의 Index쌍을 총 (n - 1)개 출력
이렇게 출력만 해주면 정답이 되었다.
다음은 제출코드이다. 여러번 고친 코드여서, 쓸모없거나 비효율적인 부분이 있을 수 있다.
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
// 전역변수
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int tc;
cin >> tc;
while(tc--) {
int n, e = 0, o = 0, cnt = 0;
cin >> n;
int arr[2 * n + 1] = {0};
vector<int> even;
vector<int> odd;
for(int i = 1; i < 2 * n + 1; i++) {
cin >> arr[i];
if(arr[i] % 2 == 0) {
e++;
even.push_back(i);
} else {
o--;
odd.push_back(i);
}
}
if(e == 0 || o == 0) {
for(int i = 1; i <= n && cnt < n - 1; i++) {
cout << 2 * i - 1 << " " << 2 * i << "\n";
cnt++;
}
} else {
for(int i = 0; i < even.size() / 2 && cnt < n - 1; i++) {
cout << even[2 * i] << " " << even[2 * i + 1] << "\n";
cnt++;
}
for(int j = 0; j < odd.size() / 2 && cnt < n - 1; j++) {
cout << odd[2 * j] << " " << odd[2 * j + 1] << "\n";
cnt++;
}
}
}
return 0;
}C번 Number Game - 성공
정수 N이 주어진다. Ashishgup과 FastestFinger가 게임을 한다. 각각의 플레이어의 턴에는 다음과 같은 행동을 할 수 있다. 현재 N을 1보다 큰 홀수로 나누거나, N이 1보다 크다면 1을 뺄 수 있다. 자신의 턴에 아무런 행동을 할 수 없다면, 자신은 패배하고 상대방이 승리한 것이다. 정수 N이 주어졌을 때 누가 승리했는지 출력하시오.
일단 입력인 N의 최댓값이 10^9이므로, N에서 경우를 모두 탐색하던가 하는 방법은 할 수 없었다. 그래서 생각을 천천히 해보았는데, N의 상태가 소수인지, 홀수인지, 짝수인지 등에 따라서 승자를 확인할 수 있었다.
기본적으로 N이 1이면 상대 플레이어 FastestFinger이 승리한다.
가장 쉬운 상태는 N이 소수인 경우이다.
소수는 2, 3, 5, 7, ...과 같이 있는데, 2를 제외하면 모두 홀수이다. 뒤에서도 설명하겠지만, 현재 상태가 홀수이면 승리한다. 또한 2의 경우 현재 플레이어가 2에서 1을 빼는 행동을 한다면, 다음턴 플레이어는 아무런 행동을 할 수 없으므로 승리한다. 즉, N이 소수인경우 현재 플레이어 Ashishgup이 승리한다.
다음은 N이 홀수인 경우이다.
문제의 조건에 N을 1 이상의 홀수로 나눌 수 있고, 앞에서 N이 1인경우를 확인했기 때문에, 현재 N을 N으로 나누면 1이 되므로 승리한다. 즉, N이 홀수인경우 현재 플레이어 Ashishgup이 승리한다.
마지막으로 N이 짝수인 경우이다.
짝수는 또 다음과 같은 경우 두 가지로 나눌 수 있다.
1. N이 2의 배수인 경우 (즉, N = 2 * 2 * ... * 2) 이 경우, 선택지는 오직 1을 빼는 행동뿐이고, 상대방 턴에 N이 홀수이므로 패배한다. 즉 N이 2의 배수이면 상대 플레이어 FastestFinger이 승리한다.
2. 그 이외의 짝수인 경우 (즉, N = 짝수 * 홀수)
이때 먼저 2가 2개 이상 있는 경우 승리할 수 있다. 예를 들면, N = 2 * 2 * 3 * 3 과 같은 경우, N에서 홀수인 소인수들을 모두 나누어서 2 * 2로 만든다면, 1의 경우와 같이 상대방이 2의 배수를 가지고 있으므로, 승리한다. 즉, N의 소인수에 2가 2개 이상 있으면 현재 플레이어 Ashishgup이 승리한다.
이제 2가 단 한개만 곱해져 있을때를 생각해보자. 이 경우 소인수를 확인해서, 홀수인 소인수가 2개 이상 있으면 승리할 수 있다. 다시한번 예를들면, N = 2 * 3과 N = 2 * 3 * 3인 경우를 생각해보자. 모든 케이스에서 1을 빼는 선택지는 패배한다. (짝수에서 1을 빼면 홀수이므로, 상대방이 홀수이면 패배함.) 그러므로, 홀수인 소인수로 나누는 경우를 생각해봐야하는데, 만약 홀수인 소인수가 한개이면, 상대방이 2, 즉 소수를 가지고 있으므로 패배한다. 그렇지 않으면, N을 2 * (소수) 꼴로 만들어서 상대방에게 넘기면 승리할 수 있다.
아래는 제출코드이다.
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
// 전역변수
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int maxnum = 1000000;
bool prime[1000000 + 1];
memset(prime, 1, sizeof(prime));
prime[0] = prime[1] = false;
vector<int> pnum;
for(int i = 2; i < 1000000 + 1; i++) {
if(!prime[i]) continue;
pnum.push_back(i);
for(int j = 2; i * j < 1000000 + 1; j++) {
prime[i * j] = false;
}
}
int tc;
cin >> tc;
while(tc--) {
int n;
bool nprime = true;
cin >> n;
for(int i = 0; i < pnum.size(); i++) {
if((int)sqrt(n) < pnum[i]) break;
if(n % pnum[i] == 0) {
nprime = false;
break;
}
}
if(n == 1) {
cout << "FastestFinger\n";
} else if(nprime) {
cout << "Ashishgup\n";
} else if(n % 2 == 1) {
cout << "Ashishgup\n";
} else {
if(POW2(n)) {
cout << "FastestFinger\n";
} else {
int cur = n;
int tcnt = 0;
while(1 < cur && cur % 2 == 0) {
cur /= 2;
tcnt++;
}
if(1 < tcnt) {
// n에 2가 2개이상 있음. - n을 2의 배수로 만듬
cout << "Ashishgup\n";
} else {
// n에 2가 1개만 있음.
n = n / 2;
bool nextisprime = true;
for(int i = 0; i < pnum.size(); i++) {
if((int)sqrt(n) < pnum[i]) break;
if(n % pnum[i] == 0) {
if(n / pnum[i] == 1) {
nextisprime = true;
} else {
nextisprime = false;
}
break;
}
}
if(nextisprime) {
cout << "FastestFinger\n";
} else {
cout << "Ashishgup\n";
}
}
}
}
}
return 0;
}
'코드포스_Code Forces > Code Forces (Div. 2)' 카테고리의 다른 글
| [코드포스/Contest] Coderforces Round #648 (Div. 2) (0) | 2020.06.08 |
|---|---|
| [코드포스/Contest] Codeforces Round #647 (Div. 2) (0) | 2020.06.05 |
| [코드포스/Virtual] Codeforces Round #620 (Div. 2) (0) | 2020.05.30 |
