Codeforces Round 599 (Div. 2) 후기 및 문제 풀이
by 줌코딩
후기
- virtual participation으로 풀었는데 2200점이라니ㅠㅠㅠㅠㅠㅠ 지난주에 시험칠걸 그랬나ㅠㅠㅠ
- 앞 3문제의 난이도는 그닥 어렵지 않았지만 4번문제를 푸냐 못푸느냐가 관건인것 같다.
- 제대로 푼 게 아니라 어쩌다가 4번을 풀어버렸다. 뭐 이런저런 걸 떠나서 나름 만족스러운 시험이었다!
- 그리고 잔실수 줄이는 연습이 필요할 듯하다.
A. Maximum Square
- 이 문제는 4분컷 해버렸다.
- 보자마자 방법이 떠올라서 바로 구현에 들어갔다.
- n개 짜리가 n개 이상 있다면 n짜리 정사각형을 만들 수 있다.
코드
#include <cstdio>
int t, n, arr[1001];
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
for(int i = n; i >= 1; i--){
int sum = 0;
for(int j = 0; j < n; j++){
if(arr[j] >= i)sum++;
}
if(sum >= i){
printf("%d\n", i);
break;
}
}
}
}
B1. Character Swap (Easy Version)
- 이 문제는 단순히 문자열을 돌면서 각 위치 값이 다른 위치를 세서 다른 개수가 2개이면서 s1[i]와 s2[j]를 바꿨을 때 두 문자열이 같아지면 YES를 출력하면 된다.
- 문자열 길이를 10001이 아니라 1001로 해서 2번이나 틀려버렸다…ㅠㅠ
코드
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t, n;
char s1[10001], s2[10001];
int main(){
scanf("%d", &t);
while(t--){
int x[2], cnt = 0, valid = 1;
scanf("%d %s %s", &n, s1, s2);
for(int i = 0; i < n; i++){
if(s1[i] == s2[i])continue;
else {
if(cnt == 2){
valid = 0;
break;
}
x[cnt++] = i;
}
}
if(valid){
if(cnt == 1)valid = 0;
else if(cnt == 2) {
if(s1[x[0]] == s1[x[1]] && s2[x[0]] == s2[x[1]]);
else valid = 0;
}
}
if(valid)printf("YES\n");
else printf("NO\n");
}
}
B2. Character Swap (Hard Version)
- 이 문제는 B1이랑 똑같으나 바꿀 수 있는 횟수가 2n번이다.
- s1[i]와 s2[i]가 다를 때 s2[i]와 같은애가 s1[i + 1] ~ s1[n - 1] 중에 있으면 s1[i], s2[i]를 swap하고 s2[i]랑 찾은 값으로 swap해서 총 2회 swap으로 해결할 수 있다.
- 만일 s2[i + 1] ~ s2[n - 1] 중에 있으면 s1[i]와 그냥 swap해줘서 1번의 swap으로 s1[i]와 s2[i]를 같게 해줄 수 있다.
- 두 경우 모두 없다면 No를 출력하게 한다.
- 그러므로 이 때 최대 교환 횟수는 2n이 된다.
코드
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t;
int main(){
cin >> t;
while(t--){
int valid = 1, n;
char s1[52], s2[52];
cin >> n >> s1 >> s2 ;
vector<int> mx, my;
for(int i = 0; i < n; i++){
if(s1[i] == s2[i])continue;
else {
int find = 0;
for(int j = i + 1; j < n; j++){
if(s2[i] == s2[j]){
mx.push_back(i), my.push_back(j);
swap(s1[i], s2[j]);
find = 1;
break;
}
}
if(find)continue;
for(int j = i + 1; j < n; j++){
if(s2[i] == s1[j]){
mx.push_back(i), my.push_back(i);
swap(s1[i], s2[i]);
mx.push_back(j), my.push_back(i);
swap(s1[j], s2[i]);
find = 1;
break;
}
}
if(!find){
valid = 0;
break;
}
}
}
if(!valid){
cout << "NO\n";
continue;
}
cout << "YES\n";
cout << mx.size() << '\n';
for(int i = 0; i < mx.size(); i++){
cout << mx[i] + 1 << ' ' << my[i] + 1 << '\n';
}
}
}
C. Tile Painting
- 처음으로 1500점짜리 문제를 풀어봤다. (실제로 셤을 봤어야 했다….ㅎㅎ)
- 몇가지 경우를 돌려보니 소수가 1개라면 무조건 소수 만큼 색을 뽑을 수 있고
- 소수가 2개 이상이면 1개의 색 밖에 안된다.
- 근데 예외가 있는데 제일 작은 소수로 나머지 소수가 다 나눠진다면 그 때도 소수가 1개인 경우로 볼 수 있다.
- 소수가 없다면 n개의 색을 출력한다.
- 혹시나 해서 제출했는데 맞아버렸다…ㅎㅎㅎ(다음에도 1500점 문제를 풀수있을까..?ㅠㅠ)
코드
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
long long n, m, val, cnt;
//sqrt(n)보다 작은 약수를 구하고 이를 이용해서 또 다른 약수를 찾아
int main(){
scanf("%lld", &n);
m = sqrt(n);
for(long long i = 2; i <= m; i++){
if(n % i == 0){
if(val == 0)val = i, cnt++;
if(i % val != 0)cnt++;
long long next = n / i;
if(next % val != 0)cnt++;
}
}
if(cnt == 1)printf("%lld", val);
else if(cnt >= 2)printf("1");
else printf("%lld", n);
}
느낀점
- Div.2는 진짜 잘해야 본전이 될것같은 느낌이 강하다… 화요일에 1500점 뚫을 수 있을까..?ㅋㅋ
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS