Sechack
Codeforces div2 3솔의 벽을 깨다(virtual) 본문
원래 작년 이때쯤에 PS조금 건드려보고 코포도 조금 찍먹하다가 접고 계속 해킹만 했었는데 한달전쯤부터 PS를 제대로 하기 시작했다. 앞으로도 안접고 적어도 오렌지 이상 될때까지는 쭉 할거같다.
새해기념으로 kwoncycle 님과 코포 버추얼을 돌렸다. 그레이(본인)와 오렌지가 같이 하는거라 div1 + div2로 돌렸다.
https://codeforces.com/contest/1844
Dashboard - Codeforces Round 884 (Div. 1 + Div. 2) - Codeforces
codeforces.com
요거 돌렸는데 생각보다 매우 만족스러운 결과를 뽑아내서 기분이 좋았다.
태어나서 처음으로 div2이상에서 3솔을 했다. ><
퍼포먼스도 그린 퍼포먼스가 나왔다. 계속 이정도 퍼포먼스만 떠준다면 그레이 탈출을 할 수 있겠지...
그래프를 보면 지금 거의 그린에 가까워지긴 했는데 이제 코포 치기가 무섭다. 그린 이상 퍼포먼스를 내려면 div2 2솔을 빠르게 안정적이게 할 수 있어야 하고 가끔은 3솔도 해줘야 한다. 하지만 현재의 나는 b를 못풀때도 은근 있고 a, b를 푸는 속도도 그다지 빠르지 않다. 그래서 이제부터는 백준, 코포 버추얼 등을 병행하면서 안정적으로 그린 이상 퍼포먼스를 낼 수 있을때까지 연습한 뒤에 코포에 다시 복귀하려고 한다. 곧 BoB 3차 경연단계(Top30)라서 어차피 코포 칠시간도 별로 없을거니까 틈틈히 버추얼 돌리고 백준 풀면서 실력을 키운 뒤에 다시 레이팅을 올릴 생각이다. 올해 안에 블루 찍어야지..ㅎㅎ
이제부터 문제 풀이다.
A. Subtraction Game
Problem - A - Codeforces
codeforces.com
$n$개의 돌이 있고 두 명의 플레이어가 게임을 할 때 각 플레이어는 번갈아가면서 게임을 하고 자기턴에 정확히 $a$개 또는 b개의 돌을 제거할 수 있다. $a < b$이고 자기 턴에 돌을 제거할 수 없는 플레이어가 지게되는 게임인데 첫번째 플레이어가 어떤 선택을 하던 두번째 플레이어가 이기게 만드는 $n$값을 구하면 되는 문제이다.
그냥 $n$값으로 $a+b$를 선택하면 첫번째 플레이어가 $a$개를 제거하던 $b$개를 제거하던 지게 된다. 딱히 생각할것도 없는 문제라 3분만에 AC를 띄웠다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
using namespace std;
#define ll long long
#define ull unsigned long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int a, b;
cin >> a >> b;
cout << a+b << "\n";
}
return 0;
}
B. Permutations & Primes
Problem - B - Codeforces
codeforces.com
임의의 수열이 주어지면 해당 수열의 MEX는 수열에 없는 가장 작은 양의 정수라고 정의한다. 즉 $MEX(1, 2, 3, 4, 5) = 6$, $MEX(1, 3, 4, 5, 6) = 2$인 셈이다. 그리고 배열 $a1, a2, ..., an$의 소수성은 $1 \leq l \leq r \leq n$이고 $MEX(al, ..., ar)$ 이 소수인 경우의 쌍 $(l, r)$의 수로 정의했을때 1부터 $n$까지의 순열 중 소수성이 가장 큰 수열을 찾는 문제다.
결국은 어떤 수열의 모든 부분 수열에 대한 $MEX$값이 소수인 값이 가장 많도록 1부터 $n$까지의 수를 잘 배치해서 수열을 뽑아내면 되는거다. 문제를 이해한 직후에는 뇌정지가 올 수 있지만 쉬운 문제다. $MEX$가 소수가 되려면 일단 수열에 1이 무조건 포함되어 있어야 한다. 1이 없으면 수열에 뭐가 있던 $MEX$는 1이 되어버린다. 따라서 1을 최대한 많은 부분 수열에 들어가게 배치하려면 가운데에 배치할수록 이득이다. 여기서 조금 더 생각을 뻗어나가면 수열에 1이 있으면 2, 3은 둘중에 하나만 있어야 한다. 두개 다 있으면 $MEX$가 4가 되면서 소수가 아니게 되기 때문이다. 따라서 1을 가운데 두고 2, 3이 부분수열에서 같이있는걸 최대한 방지하려면 2와 3은 최대한 멀리 떨어뜨려야 한다.
즉 1은 정가운데 배치하고 2와 3은 각각 수열의 맨 끝에 배치하게 되면 이 문제를 해결할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
using namespace std;
#define ll long long
#define ull unsigned long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) v[i] = i+1;
if(n > 2){
swap(v[2], v[n-1]);
swap(v[n/2], v[0]);
if(n > 3) swap(v[0], v[1]);
}
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << "\n";
}
return 0;
}
이런걸 왜 52분이나 걸렸냐면 처음에 1을 가운데 두는것까지만 생각하고 바로 구현해서 틀린거랑 if(n > 3)처리 안해주고 맞왜틀한 시간이랑 문제 이해하는 시간 뭐 이런거 다 합해서 52분이 아닐까 싶다. 이런 문제는 빨리 풀어야 하는데 너무 느린듯...
C. Particles
Problem - C - Codeforces
codeforces.com
버추얼 도중에 못풀고 업솔빙한 문제이다. 1시간 이상 고민했지만 어느정도 접근한 이후부터 도저히 진도가 안나가길래 D로 넘어갔고 어느정도 접근한것마저 정풀과는 아예 다른방향이었다.
수열이 주어지면 해당 수열에서 아무 원소나 골라서 제거할 수 있다. 그리고 제거될때 제거되는 원소 양옆에 다른 원소가 존재한다면 그 두 원소는 합쳐진다. 즉 1, 2, 3, 4, 5 이런 수열에서 3을 제거하면 3양옆에 있는 2와 4가 합쳐지면서 1, 6, 5가 되는것이다. 그리고 또다시 1을 제거하면 1의 왼쪽에는 원소가 존재하지 않으므로 합쳐지지 못하고 그냥 1만 제거되면서 6, 5가 남게 된다. 이런식으로 수열에서 임의의 원소를 골라서 계속해서 제거해나갈때 마지막에 남을 수 있는 값중 가장 큰 값을 구하는 문제다.
먼저 한가지 관찰을 할 수 있는데 홀수번째 원소와 짝수번째 원소는 무슨짓을 해도 절대 합쳐질 수 없다는 것이다.
버추얼 도중에도 비슷한 관찰을 했었던걸로 기억하는데 생각이 너무 산으로 갔었다. 아무튼 이 관찰 하나만 하면 이 문제는 쉽게 풀 수 있다. 결국 홀수번째는 홀수번째 원소, 짝수번째는 짝수번째 원소랑만 합칠 수 있고 여기서 조금만 더 생각해보면 인덱스의 홀짝이 같다는 가정하에 합치고 싶은 값들은 전부 합칠 수 있고 반대로 빼고싶은 값들은 전부 빼버릴 수 있음을 알 수 있다. 따라서 홀수 인덱스랑 짝수 인덱스를 분리해서 음수일경우 안더하고 양수일경우 더해줘서 홀짝에 대한 각각의 최적해 2개를 도출할 수 있고 둘중 더 큰 값이 문제에서 요구하는 마지막에 남는 최대값이다. 한가지 조심해야되는건 모든 값이 음수일수도 있으니까 이런 경우만 따로 처리해주면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
using namespace std;
#define ll long long
#define ull unsigned long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
ll ans = 0, ans1 = 0, z = -1000000000;
for(int i = 0; i < n; i++){
ll v;
cin >> v;
z = max(v, z);
if(i%2) ans += max(v, 0ll);
else ans1 += max(v, 0ll);
}
if(z < 0) cout << z << "\n";
else cout << max(ans, ans1) << "\n";
}
return 0;
}
D. Row Major
Problem - D - Codeforces
codeforces.com
지문만 봐서는 문제에서 뭘 요구하는건지 이해가 잘 안갈수도 있는데 예시를 보면 직관적으로 이해할 수 있다.
위의 예시처럼 문자열을 $x$등분해서 만들 수 있는 모든 격자에 대해서 인접한 같은 문자가 없는 길이가 $n$인 문자열 중에 같은 문자가 최소로 있는 문자열을 구하는 문제이다.
일단 가로로 인접한 문자가 같은 경우를 생각해보면 aaaaa와 같이 같은 문자가 연속되지만 않으면 된다. 즉 abababababab이런식으로 연속되지만 않게 해도 모든 격자에 대해서 가로로 인접한 문자가 같을 일은 없다. 그러면 이제 세로로 인접한 문자가 같을 경우를 생각해야되는데 이것도 간단하다. 문자열을 $x$등분해서 격자를 만들때 $x$에 들어갈 수 있는 숫자가 결국에는 $n$의 약수일수밖에 없기 때문이다. 조금 더 직관적이게 예시를 하나 들자면 길이가 $n = 12$라고 가정했을때 격자를 만들 수 있는 경우는 $1 \times 12, 2 \times 6, 3 \times 4, 4 \times 3, 6 \times 2, 12 \times 1$이다. 따라서 세로로 인접한 문자가 같게 되는 경우는 $n$의 약수 간격에 같은 문자가 있는 경우이다.
그러니까 간단하게 $n$의 약수가 아닌 가장 작은 수만큼 다른 문자를 1개씩 가진 문자열을 길이가 $n$이 될때까지 반복해서 출력하면 풀 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
using namespace std;
#define ll long long
#define ull unsigned long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 1;
if(n > 1){
for(int i = 2; i <= n; i++){
ans = i;
if(n%i) break;
}
}
int i = 0;
while(i < n){
for(int j = 0; j < ans; j++){
if(i >= n) break;
cout << (char)(j+'a');
i++;
}
}
cout << "\n";
}
return 0;
}
개인적으로는 이 문제가 B보다도 쉽게 느껴졌다. 그리고 실제로 풀이 시간만 따지면 B보다 훨씬 빨랐다. 개인적인 생각이긴 한데 A - D - B - C로 재배치를 했어야 딱 난이도 순서대로 정렬이라 생각하는데... 뭐 사람마다 생각은 다를 수 있으니 이 문제가 D에 배치된것도 합리적인 이유가 있을것이다.
'PS > Codeforces' 카테고리의 다른 글
| Codeforces Round #815 (Div.2) 후기 (0) | 2022.08.19 |
|---|
