[CF] Codeforces Round 901 (Div. 2)

https://codeforces.com/contest/1875

Dashboard - Codeforces Round 901 (Div. 2) - Codeforces

그린 행동을 해버렸다. 1시간 반 가까이 C를 못 풀어서 멘탈이 나가서 탈주해 버렸다. 라운드 치고 화가 잔뜩 나서 산책 좀 하다가 집에 돌아와서 C, D 업솔빙을 하고 잤다.
솔직히 이럴 때 빠르게 D를 보고 멘탈 관리를 했어야 하는데, 판단을 잘못했다.
요즘 코포를 너무 못해서 위기감을 느끼며 평소에 안 하던 업솔빙도 하고 글도 쓴다.
 

A. Jellyfish and Undertale (00:09)

tool은 타이머가 1일 때 쓰는 게 항상 최적이라는 점을 이용하면 된다.
 

B. Jellyfish and Game (00.30)

$a_i, b_i$의 최대 최소를 누가 가지고 있는 지 4가지 상태로 나타낸 뒤에 최적으로 시행을 해보자.
첫 라운드 종료 시에 항상 Jellyfish가 최대, Gellyfish가 최소를 가지게 된다.
이 상태에서 라운드를 계속 진행하면, Jellyfish가 최대, Gellyfish가 최소를 가지는 상태와 Jellyfish가 최소, Gellyfish가 최대를 가지는 상태가 번갈아 나타나게 된다.
첫 라운드만 직접 해주고, 나머지는 기우성에 따라 처리해주면 된다.
 

C. Jellyfish and Green Apple (Upsolved)

최적으로 나누었을 때 한 사람이 가지게 될 사과 조각이 어떠한 비트에 대응된다는 사실은 직접 써보면 알 수 있다.
나는 대회 내내 여기서 진전이 없었다. 
반으로 자르는 횟수를 구해야 하는데, 이 방식을 쉽게 처리할 방식을 찾지 못했다. 
여기서부터는 크게 2가지 방법이 있다.
 
풀이1. 조각의 개수 관리하기

void solve(void) {
  int n, m; cin >> n >> m;
  n %= m;
 
  long long ans = 0;
  int cnt = 0;
  while (n != 0) {
    ans += n;
    n *= 2;
    n %= m;
    cnt++;
    if (cnt > 1000) {
      ans = -1;
      break;
    }
  }
  cout << ans << "\n";
}

 현재 조각을 모두 자르면 조각의 개수가 2배가 되고, 이를 정확히 m명에게 나눠주어야 한다는 사실을 이용한 풀이이다.
while문을 한 번 돌 때마다, n번 자르고 나눠줄 수 있는 걸 나눠주면 n%m개의 조각이 남는다.
우리 학회 1학년 친구의 코드이다. 멋지다.
 
풀이2. 조각의 개수 계산하기

ll n, m;
 
void solve()
{
	cin >> n >> m;
	n %= m;
	ll g = gcd(n, m);
	ll a = n / g, b = m / g;
 
	if (__builtin_popcount(b) > 1) cout << "-1\n";
	else cout << 1ll * __builtin_popcount(a) * m - n << '\n';
}

1번 자르면 조각의 개수가 1개 늘어난다는 점을 이용한 풀이이다. 결과적으로 남은 조각의 개수로부터 역추적하는 느낌이다.
결국 한 사람이 갖게 될 조각의 개수가 __builtin_popcount(a)이고 m명이 있으므로, 결과적으로 남은 조각의 개수는 둘을 곱한 것이다. 처음에 1개의 조각이 있던 것이 아니라, n개의 조각이 있었으므로 여기서 n을 빼면 답이 된다.
 
두 풀이 모두 조각의 개수에 대해 생각하는 것이 관건이었는데, 나는 조각의 크기와 개수를 동시에 생각하려고만 해서 못 풀었던 것 같다. 개수만 고려해도 저절로 크기도 맞춰진다는 점을 생각해 풀었어야 할 것 같다. 
 
이 풀이가 에디토리얼에 소개된 풀이인데, 마지막 식이 너무 이해가 안 되어서 질문을 했는데, 누군가가 친절하게 답해줘서 너무 기뻤다...
 

상황적으로 이해하려면 전자를, 식으로 받아들이려면 후자를 보면 될 것 같다.
 

D. Jellyfish and Mex (Upsolved)

• mex값을 계속해서 줄여나가면서 원소를 제거해야 하므로, $a_i$가 큰 것부터 제거해야 한다.
• $a_i$값이 동일한 것들이 여러 개 있으면, 연속적으로 전부 제거해야 한다.

위 두 가지 관찰을 이용해서 $a_i$ 내림차순으로 정렬해놓고, $O(n^2)$ dp를 하면 된다.
 
 
아이디어보다 관찰을 먼저 하자.
어려운 걸 풀자.
업솔빙을 하자.
오래 고민한답시고, 답 안보고 문제 던져놓지 말자.
그냥 빠르게 답보고 배우자.