Codeforces Round #554(Div.2) A~D
정말 오랜만에 풀이를 올린다. 성실하게 써야 하는데..
A. Neko Finds Grapes
n개의 숫자들로 이루어진 배열 a와 m개의 숫자들로 이루어진 배열 b가 주어진다. 이때 배열 a의 숫자와 b의 숫자를 하나씩 매칭해서 더한 것이 홀수가 되는 쌍이 최대한 많도록 매칭하는 문제다. 그때의 매칭 수를 구하면 된다.
두 수를 더해서 홀수가 되기 위해서는 (짝수, 홀수) 혹은 (홀수, 짝수) 쌍이 되어야 하기 때문에 a,b 배열의 홀수 개수, 짝수 개수를 각각 저장해 놓고 홀수-짝수를 매칭할 수 있는 쌍 개수를 구해주면 된다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
int codd = 0, ceven = 0, kodd = 0, keven = 0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
int c;
cin >> c;
if (c % 2 == 0) { ceven++; }
else { codd++; }
}
for (int i = 0; i < m; i++) {
int k;
cin >> k;
if (k % 2 == 0) { keven++; }
else { kodd++; }
}
int ans = min(keven, codd) + min(kodd, ceven);
cout << ans << "\n";
return 0;
}
B. Neko Performs Cat Furrier Transform
나는 xor이 너무너무 싫다..버추얼 돌릴 때도 C번을 풀고서 이걸 풀지 못했다..1시간 동안 시도를 하긴 했는데 나중에 보니 개삽질이었다. 근데 코포에는 xor 문제가 단골급으로 나온다....
어떤 수가 2m - 1 꼴일 때, 그 수를 perfect하다고 한다. 주어진 수에 연산을 적용해서 그 수를 perfect하게 만들어야 한다. 주어진 수 x에 대해 우리가 하는 연산은 다음과 같다.
홀수 번째 연산 : 어떤 정수 n을 골라 $$ x \oplus\ (2^n-1) $$ 을 시행한다.
짝수 번째 연산 : x에 1을 더한다.
이 연산을 40회 미만으로 진행해서 수를 perfect하게 만들어야 한다. 우리는 주어진 수를 perfect하게 만드는 데 필요한 연산 횟수와, 그러는 과정 중 홀수 번째 연산에서 쓰이는 정수들을 알아내야 한다.
2n -1 은 이진수로 나타냈을 때 11..111(1이 n개)로 나타난다. 이때 주어진 수 x와 이진수 자릿수가 같은 2n -1 을 xor하면 x의 이진수 표현 중 1은 모두 0이 될 것이고 0은 모두 1이 될 것이다. 즉, 적어도 최상위 비트 1 하나는 무조건 사라진다. 그런데 주어진 수는 100만 미만이므로 220 보다 작다. 따라서 아무리 못해도 40회 안에 주어진 수를 1(perfect한 수 중에 하나)로 만들 수 있음이 보장된다. 그러면 어떻게 해야 주어진 수를 perfect하게 만들 것인가?
그냥 시키는 대로 해주면 된다. 주어진 수 x와 이진수 자릿수가 같은 2n - 1을 골라서 xor 시키고, 1을 더해주는 걸 반복하면서 수가 perfect한지 계속 체크하고 perfect해지면 답을 출력해 주면 된다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) {
if (b == 0) { return a; }
return gcd(b, a % b);
}
int check(int n) { //2^n-1꼴인지
n += 1;
while (n % 2 == 0) { n /= 2; }
if (n == 1) { return 1; }
else { return 0; }
}
int first(int n) { //이진수로 몇 자리 수인지를 알아낸다
int r = -1;
for (int i = 30; i >= 0; i--) {
if ((n >> i) & 1) { r = i; break; }
}
return r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int cnt = 0;
vector<int> ans;
while (check(n) == 0) { //perfect해질 때까지
cnt++;
if (cnt % 2 == 0) { n++; continue; }
int z = first(n);
if (n != (1 << z)) { z++; } //같은 이진수 자릿수를 만들기 위해서
ans.push_back(z);
n = n ^ ((1 << z) - 1);
//cout << z << "\n";
}
cout << cnt << "\n";
if (!ans.empty()) {
for (int k : ans) {
cout << k << " ";
}cout << "\n";
}
return 0;
}
C. Neko does Math
a,b 두 수가 주어진다. 이때 a+k, b+k의 최소공배수(lcm)가 가장 작아지는 k를 구해야 한다.
처음 생각하기로는 lcm(a,b)=a*b/gcd(a,b) 에 의해서, lcm이 최소가 되기 위해서는 gcd가 최소가 되어야 하므로 단순히 gcd(a+k,b+k)가 최대가 되도록 만들면 된다고 생각했다. 그래서 어떻게든 그런 코드를 짰다. a%num==b%num 인 제일 큰 num이 gcd(a+k, b+k) 를 최대화하는 gcd일 거라고 생각한 그런 논리였다.
그런데 내가 생각하지 못한 부분은 k가 늘어나면 (a+k)*(b+k)도 늘어나서 lcm에 영향을 준다는 사실이었다. 단순히 gcd 최대화만으로는 부족했다. 따라서 가능한 모든 k에 대해 실제로 lcm(a+k, b+k)가 최소인지 확인해 주는 과정이 필요했다.
이때 생각해야 할 부분은 gcd(a+k, b+k) = gcd(a-b, b+k) 에 의해, a+k, b+k 의 gcd는 a-b의 약수여야 한다는 것이다. 따라서 a-b의 약수들에 대해서만 k를 어떻게든 구해서, lcm(a+k, b+k)가 최소가 되는지 하나하나 확인해 주면 된다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) {
if (b == 0) { return a; }
return gcd(b, a % b);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll a, b, mod, g = 0;
cin >> a >> b;
if (a < b) { swap(a, b); }
vector<ll> div;
for (ll i = 1; i * i < a - b; i++) {
if ((a - b) % i == 0) {
div.push_back(i);
div.push_back((a - b) / i);
}
}
sort(div.begin(), div.end(), greater<ll>());
ll lcm = 9000000000000000000;
ll ans = 0;
for (ll num : div) {
if (a % num == b % num) {
if (a % num == 0) {
ll tmp_lcm = (a * b) / gcd(a, b);
if (lcm > tmp_lcm) {
lcm = tmp_lcm; ans = 0;
}
}
else {
ll k = (num - (a % num));
ll tmp_lcm = (a + k) * (b + k) / gcd(a + k, b + k);
if (lcm > tmp_lcm) {
lcm = tmp_lcm; ans = k;
}
}
}
}
cout << ans << "\n";
return 0;
}
D. Neko and Aki's Prank
실제 버추얼을 돌 때는 B를 잡고 있느라 문제를 읽지도 못했다. 그리고 지금도 솔직히 내 깜냥에 현장에서 풀 수 있을 거라고 생각되지도 않지만..일단 1000명 이상 풀었으므로 내 기준에 따라 업솔빙을 한다.
트라이와 관련이 있는 문제 같지만 그냥 문제 설명에 쓰였을 뿐 트라이 자료구조와는 관련이 없다. 괄호 문자열을 구성하는 데 쓰인 트라이에서 서로 다른 간선을 얼마나 고를 수 있는지에 관한 문제이다. 여는 괄호 a개, 닫는 괄호 b개에다가 그 간선을 선택할지에 대한 정보를 담은 3차원 dp로 해결할 수 있다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int mod = 1000000007;
int dp[1005][1005][2];
void solve(int a, int b) { //a>b
if (dp[a][b][0] != -1) { return; } //이미 선택
if (a == -1 || b == -1 || a < b) { return; }
//여는 괄호, 닫는 괄호는 0개 이상이어야 한다.
//그리고 balanced이므로 닫는 괄호가 더 많은 상황은 오지 않는다
dp[a][b][0] = 0; dp[a][b][1] = 0;
//a개의 여는괄호, b개의 닫는괄호가 있고 그 간선을 선택했을 경우
solve(a - 1, b);
solve(a, b - 1);
if (a != 0 && b != 0 && a > b) {
dp[a][b][0] = (max(dp[a - 1][b][0], dp[a - 1][b][1]) + max(dp[a][b - 1][0], dp[a][b - 1][1])) % mod;
if (dp[a - 1][b][0] > dp[a - 1][b][1] || dp[a][b - 1][0] > dp[a][b - 1][1]) { dp[a][b][1] = (dp[a][b][0] + 1) % mod; }
//만약 이번 간선을 그냥 선택할 수 있을 경우이다
else { dp[a][b][1] = (max(dp[a - 1][b][0] + dp[a][b - 1][1], dp[a - 1][b][1] + dp[a][b - 1][0]) + 1) % mod; }
//둘 중 하나만 선택해야 한다
}
else if (b != 0) {
dp[a][b][0] = max(dp[a][b - 1][0], dp[a][b - 1][1]);
dp[a][b][1] = (dp[a][b - 1][0] + 1) % mod;
}
else if (a != 0) {
dp[a][b][0] = max(dp[a - 1][b][0], dp[a - 1][b][1]);
dp[a][b][1] = (dp[a - 1][b][0] + 1) % mod;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 0; i < 1005; i++) {
for (int j = 0; j < 1005; j++) {
dp[i][j][0] = -1;
dp[i][j][1] = -1;
}
}
int n;
cin >> n;
solve(n, n);
cout << max(dp[n][n][0], dp[n][n][1]) << "\n";
//여는괄호 n개, 닫는괄호 n개
return 0;
}