넷째 판은 Good Bye 2023이었고, 모든 사람을 대상으로 Rated였다.
항상 그래왔듯이 A, B를 15분동안 밀고, C도 자신있는 게임이론 류의 문제라서 금방 풀었다. 그리고 1시간 30분동안 D, E랑 싸우다가 패배하고, 그러다가 대회 종료 5분 전에 D풀이를 떠올리고 결국 시간 안에 못 구현하고 끝났다.
D는 말이 많은 문제였지만, 그래도 대회 시간 안에 풀이가 떠올랐기 때문에 풀 문제를 못 푼것 같아서 아쉬웠다. 차라리 뒤에 문제들을 쳐다보지도 않고 D에 집중했으면 풀 수도 있었을 것 같다. 이런 것이 경험 차이라고 생각하고, 앞으로 계속 연습해야 할 것 같다.
A. 2023
https://codeforces.com/contest/1916/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n, k;
cin >> n >> k;
bool able = true;
int v = 2023;
for (int i = 0; i < n; i++) {
int input;
cin >> input;
if (v % input != 0) {
able = false;
}
v /= input;
}
if (able) {
cout << "Yes" << '\n';
cout << v << " ";
for (int i = 1; i < k; i++) {
cout << 1 << " ";
}
cout << '\n';
}
else {
cout << "No" << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 단순 구현 문제이다. 먼저 b가 2023의 인수분해 중 일부인지 확인하는 것은 나머지 연산으로 하면 되고, k개의 수를 출력할 때는 1도 출력할 수 있기 때문에, 첫번째에 곱해서 2023이 되는 수를 출력하고 나머지를 1로 출력하면 된다.
b를 전부 곱한 뒤 그 수로 2023을 나눠보는 방법도 있는 것 같지만, overflow를 처리해줘야 하고, 나는 그냥 b로 순서대로 나누는 식으로 구현했다.
B. Two Divisors
https://codeforces.com/contest/1916/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int GCD(int a, int b) {
if (b == 0) {
return a;
}
return GCD(b, a % b);
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int a, b;
cin >> a >> b;
int g = GCD(b, a);
if (a == g) {
cout << b * (b / a) << '\n';
}
else {
cout << (b / g) * a << '\n';
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 b, a를 가장 큰 두 약수로 가지는 수 x를 출력하는 문제이다. 이때, x가 무조건 존재한다는 조건이 있기 때문에 문제는 어렵지 않게 풀린다. 두가지 경우를 나눠서 생각하면 정답을 찾을 수 있다.
1. b가 a의 배수일 때
b = a * d 라고 하자. d는 무조건 소수이다. 왜냐하면 p > 1, q > 1에 대해 d = p * q라고 하면 b > p * a > a 인데, p는 x의 약수이다. 그러므로 a가 x의 두번째로 큰 약수라는 조건에 위배된다.
그리고 x = b * y라고 하자.
y < d라면 b = x / y > x / d > x / (d * y) = a 이고, b보다 작지만 a보다 큰 x / d라는 x의 약수가 존재하기 때문에 모순이 생긴다.
y > d라면 x / d > x / y = b 인데, b보다 큰 x / d라는 x의 약수가 존재하기 때문에 모순이 생긴다.
그러므로 y = d 이고, x = b * d = b * (b / a)이다. 이때, b * b / a 로 계산하면 int 범위에서 overflow가 발생하기 때문에 괄호는 풀어주지 않는다.
2. b가 a의 배수가 아닐 때
x의 소인수 중 가장 작은 두개를 p, q라고 하자(p < q). b * p = x, a * q = x이다. (예외는 x가 p ^ 2의 약수일 때인데, 이것은 경우 1에 해당된다.)
그러면 x / (p * q)는 b, a의 GCD가 된다. 왜냐하면 b * p = a * q 이므로 b도 q의 약수이고, a도 p의 약수이다(p와 q가 소수이므로). 그리고 b = q * g1, a = p * g2라고 하면 (q * g1) * p = (p * g2) * q가 되고, g1 = g2 이므로 g1 = g2 = x / (p * q) = (b, a의 최대공약수)가 된다. 그리고 q = b / (GCD(b, a))에서 x = q * a = (b / GCD(b, a)) * a이다. (GCD는 유클리드 호제법으로 쉽게 구할 수 있다.)
두가지 경우를 if문으로 나누어서 계산하고 출력하면 된다. 증명이 어렵고 답은 쉬운 문제였는데, 실제 대회때는 그냥 출력 예시들 관찰하면서 증명 없이 감으로 풀고 맞았다.
C. Training Before the Olympiad
https://codeforces.com/contest/1916/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n;
cin >> n;
int odds = 0;
long long int curr = 0;
for (int i = 0; i < n; i++) {
int input;
cin >> input;
curr += input;
if (input % 2 == 1) {
odds++;
}
int penalty = odds / 3;
if (odds % 3 == 1 && i > 0) {
penalty++;
}
cout << curr - penalty << " ";
}
cout << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 B보다도 쉽게 느껴졌다. (홀 + 홀)이나 (짝 + 짝)은 점수 손해가 없고, (홀 + 짝)은 계산할 때마다 1씩 점수 손해가 있다. 또한 모든 계산의 결과는 짝수가 된다(* 2를 해주기 때문).
손해를 최대한 많이 보게 해야 하는 Olya는 가능하다면 무조건 (홀 + 짝)을 고를 것이다. 그리고 첫번째 순서가 Masha이기 때문에 리스트에 무조건 짝수가 존재하게 된다(리스트가 모두 홀수였더라도 첫 턴의 결과는 짝수이기 때문이다). 그러므로 Olya는 자신의 턴에 홀수가 남아있다면 무조건 1점씩 깎을 수 있고, Masha는 홀수 개수를 최대한 줄이는 쪽으로 경기를 진행한다. (홀 + 홀)을 할때는 점수 손해 없이 홀수 2개가 사라지므로, Masha는 가능하다면 (홀 + 홀)을 진행할 것이다.
그러므로 Masha는 자기 차례에 홀수 2개를 없애고, Olya는 자기 차례에 홀수 1개를 없애면서 총점을 1점씩 깎는다. 이 과정은 (홀수 개수) / 3 만큼 반복된다.
문제에서 주어진 수열에서 [0, i] (0 <= i < n)구간에 대해 구해야 하므로, 각 구간에 대해 홀수 개수를 매번 for문으로 세준다면 O(n^2)시간이 걸리기 때문에 TLE가 난다. 그래서 홀수 개수의 누적합과 구간합을 구하면서 스위핑을 하면 O(n)시간에 풀 수 있다.
홀수 개수를 3으로 나눈 나머지가 1일때는 Masha가 어쩔 수 없이 (홀 + 짝)조합을 선택해야 하므로 그것만 예외처리해주면 된다.
업솔빙
D. Mathematical Problem
https://codeforces.com/contest/1916/problem/D
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
char output[100];
int digits[10];
bool Equal(int a, int b) {
fill(&digits[0], &digits[10], 0);
while (a > 0) {
digits[a % 10]++;
a /= 10;
}
while (b > 0) {
digits[b % 10]--;
if (digits[b % 10] < 0) {
return false;
}
b /= 10;
}
return true;
}
vector<int> Seven() {
for (int i = 1000; i * i < 10000000; i++) {
int si = i * i;
vector<int> res{ si };
for (int j = i + 1; j * j < 10000000; j++) {
int sj = j * j;
if (Equal(si, sj)) {
res.push_back(sj);
if (res.size() == 7) {
return res;
}
}
}
}
return vector<int>();
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
vector<int> seven = Seven();
int T;
cin >> T;
for (int tc = 0; tc < T; tc++) {
int n;
cin >> n;
if (n == 1) {
cout << 1 << '\n';
}
else if (n == 3) {
cout << 169 << '\n';
cout << 196 << '\n';
cout << 961 << '\n';
}
else if (n == 5) {
cout << 16384 << '\n';
cout << 31684 << '\n';
cout << 36481 << '\n';
cout << 38416 << '\n';
cout << 43681 << '\n';
}
else if (n == 7) {
for (int a : seven) {
cout << a << '\n';
}
}
else {
int count = 0;
int a = 0;
for (int b = a + 1; b <= n / 2; b++) {
for (int c = b + 1; c <= n / 2; c++) {
if (b - a == c - b) continue;
int ac, bc, cc;
ac = 1, bc = 2, cc = 2;
fill(&output[0], &output[n], '0');
output[n] = 0;
output[a + a] += ac * ac;
output[a + b] += ac * bc;
output[a + c] += ac * cc;
output[b + a] += bc * ac;
output[b + b] += bc * bc;
output[b + c] += bc * cc;
output[c + a] += cc * ac;
output[c + b] += cc * bc;
output[c + c] += cc * cc;
cout << output << '\n';
count++;
if (count == n) break;
ac = 2, bc = 1, cc = 2;
fill(&output[0], &output[n], '0');
output[n] = 0;
output[a + a] += ac * ac;
output[a + b] += ac * bc;
output[a + c] += ac * cc;
output[b + a] += bc * ac;
output[b + b] += bc * bc;
output[b + c] += bc * cc;
output[c + a] += cc * ac;
output[c + b] += cc * bc;
output[c + c] += cc * cc;
cout << output << '\n';
count++;
if (count == n) break;
ac = 2, bc = 2, cc = 1;
fill(&output[0], &output[n], '0');
output[n] = 0;
output[a + a] += ac * ac;
output[a + b] += ac * bc;
output[a + c] += ac * cc;
output[b + a] += bc * ac;
output[b + b] += bc * bc;
output[b + c] += bc * cc;
output[c + a] += cc * ac;
output[c + b] += cc * bc;
output[c + c] += cc * cc;
cout << output << '\n';
count++;
if (count == n) break;
}
if (count == n) break;
}
}
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/D는 n자리의 조건에 맞는 수 n개를 출력하는 문제이다. n이 99까지 되는 것을 보고, n이 굉장히 클때는 비둘기집의 원리로 조건에 맞는 수가 굉장히 많을 것까지는 알았다. 그리고 n >= 9일때의 풀이는 대회 끝날때쯤 구현에 성공했지만, n = 7일때의 풀이를 적지 못해서 결국 제출하지 못했다. 그리고 n = 7일때는 경우가 최대 2000개 정도이고, 2000^2번의 계산 안에 구할 수 있기 때문에 그냥 Brute Force로 구현할 수 있었다.
1. n이 충분히 크다면, 0이 최대한 많이 들어가게 하면 올림수가 발생하지 않으므로 쉽게 조건에 맞는 수들을 찾을 수 있다.
n = 9일때부터 생각해보면, n = x * x라고 할때, x은 5자리수임을 알 수 있다. 이때 x를 (a > b > c) d*10^a + e*10^b + f*10^c라고 해보자. n = (d^2)*10^(2 * a) + (e^2)*10^(2*b) + (f^2)*10^(2*c) + (2*d*e)*10^(a+b) + (2*d*f)*10^(a+c) + (2*e*f)*10^(b+c)가 되고,
a*2 > a+b > 2*b > b+c > 2*c이며, a+b > a+c > b+c이므로 2*b != a+c라면 모든 자리수가 달라지며, d, e, f에 1, 2, 2를 대입하면 올림수가 발생하지 않으므로 임의의 a, b, c에 대해 3가지 x를 만들 수 있다. 그리고 맨 앞자리는 0일 수 없으므로 a는 고정이고, b, c에 대해 2중 for문으로 돌리면서 x를 만들면 된다. (이 부분을 구현했을 때 대회 종료 2분 전이었다.)
2. n이 7일때는 위의 방법으로 6개의 수 밖에 만들 수 없으므로 다른 방법이 필요하다. 제곱해서 7자리 수가 되는 x는 4자리 수이고, x > 3200이면 x^2이 8자리 수가 되므로 모든 x에 대해 x^2과 y^2이 자리수를 바꿔서 만들 수 있는 y과 6개 이상인 경우를 for문으로 찾는다면, 대략 2000범위의 2중 for문이 되므로 시간 안에 풀린다. 그리고 n=7일때마다 매번 이 방법을 쓰면 시간초과가 날 수 있으니, 미리 한번 실행해놓고 결과를 vector에 저장해놓고 n=7일때마다 출력해준다.
그래서 n=1, 3, 5일때는 출력예시를 그대로 쓰고, n=7일때를 처음에 vector하나에다 저장해놓고 출력하고, n>=9일때는 1의 방법을 사용해서 출력하면 된다.