Codeforces Round 880 (Div. 2)

B,C 도 그리 쉬운 편은 아니였는데 D부터 갑자기 미친놈처럼 어려워져서 스피드포스에 성공해 44분경 C를 풀었을 때 70 몇등이였는데 대회가 끝날때까지 두자리수 스탠딩을 유지할 수 있었다.

A. Destroyer (00:02 +)Permalink

A. Destroyer

각 수들의 개수를 세둔다. 그걸 $c_i$ 라 하자.

만약 $c_{i+1} > c_i$ 라면 불가능하다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
   vi cnt(101);
   for (int i: a) cnt[i]++;
   for (int i = 1; i <= 100; i++) {
      if (cnt[i]) {
         if (cnt[i - 1] < cnt[i]) {
            cout << "NO\n";
            return;
         }
      }
   }
   cout << "YES\n";
}

B. Astrophysicists (00:27 +)Permalink

B. Astrophysicists

이때부터 지문이 심상치 않았는데, 깡수학문제가 쳐나와서 곤혹스러웠다.

어떤 사람에게 최대로 코인을 많이 뺐을 수 있는 경우는 $Q \cdot g+\left\lfloor \dfrac{g-1}{2} \right\rfloor$ 처럼 주는 방법이다.

그럼 $\left\lfloor \dfrac{g-1}{2} \right\rfloor$ 만큼 이득을 볼 수 있기 때문이다.

따라서 일단 모든 사람에게 $n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor$ 을 준 다음 생각해보자.

만약 $kg < n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor$ 라면 정답은 항상 $kg$ 이다. 모든 사람에게 다 최대로 이득을 얻을 수 있기 때문이다.

그렇지 않다면 $\left\lfloor \dfrac{kg-n \cdot \left\lfloor \dfrac{g-1}{2} \right\rfloor}{g} \right\rfloor \cdot g$ 만큼의 실버 코인은 원래 가지고 있던 코인에서 빼준다.

한명의 astrophysicist에게 모두 골드 코인을 하나 몰아준 셈이다.

이제 나머지 남은 코인 개수를 $k$ 라고 하면 한명한테 최대 $g$ 개를 줄 때 까지 골드 코인을 하나만 더 소모하면 되므로 $\left\lceil \dfrac{k}{g} \right\rceil$ 만큼 골드 코인을 더 소모하게 된다.

void solve() {
   int n, k, g;
   cin >> n >> k >> g;
   int s = k * g;
 
   int should = (g - 1) / 2;
 
   if (should * n >= k * g) {
      cout << k * g << endl;
   } else {
 
      s -= should * n;
 
      int q = s / g;
      s -= q * g;
      int ans = q;
 
      ans += (s + g - 1) / g;
 
      cout << k * g - ans * g << endl;
   }
}

C. k-th equality (00:41 +)Permalink

C. k-th equality

시간복잡도를 잘 파악하자. 오직 5개의 케이스만 $A,B,C$ 가 백만까지 나오므로 $O(N)$ 을 짜기만 하면 충분히 $O(5000000)$ 정도로 풀 수 있다는 셈이다.

$a,b,c$ 모두 가장 작은값과 큰값을 구한다. $A=5$ 라면 $a_s=10000, a_e=99999$ 같은 식이다.

$a$ 를 모두 순회하며 가능한 경우를 파악한다.

$c_s,c_e$ 를 기준으로 보면 $c_s$ 가 되기 위한 $b$의 값이 정해진다. 그건 $c_s-a$ 이다.

마찬가지로 $c_e-a$ 와 같이 $b$의 값의 범위가 나온다.

그걸 원래 $b_s, b_e$와 교차시켜서 중복되는 구간만큼 $k$ 를 빼줄 수 있다.

만약 $k$ 를 모두 뺄 수 없는 구간이 나온다면 $O(n)$으로 직접 그게 뭔지 구해줄 수 있다.

void solve() {
   int A, B, C, k;
   cin >> A >> B >> C >> k;
 
   int astart = stoll("1" + string(A - 1, '0'));
   int aend = stoll(string(A, '9'));
 
   int bstart = stoll("1" + string(B - 1, '0'));
   int bend = stoll(string(B, '9'));
 
   int cstart = stoll("1" + string(C - 1, '0'));
   int cend = stoll(string(C, '9'));
 
   // b가 정해지면 c도 정해진다.
   for (int a = astart; a <= aend; a++) {
      int bs = cstart - a;
      int be = cend - a;
 
      maxa(bs, bstart);
      mina(be, bend);
      if (bs > be) continue;
 
      int cnt = be - bs + 1;
      if (k > cnt) k -= cnt;
      else {
         for (int b = bstart; b <= bend; b++) {
            if (to_string(a + b).size() == C) {
               k--;
               if (k == 0) {
                  cout << a << " + " << b << " = " << a + b << endl;
                  return;
               }
            }
         }
      }
   }
   cout << -1 << endl;
}

D. LotteryPermalink

D. Lottery

TBD…

E. Twin ClustersPermalink

E. Twin Clusters

에디토리얼 풀이

구간합 배열로 풀 수 있다. 그리고 비둘기 집의 의해 결론적으로 정답은 항상 존재하게 된다.

입력의 제한을 심도있게 고려한다.

$n=2^{k+1}$ 이고 $g_i < 2^{2k}$ 이다.

$n$이 $2^k$ 의 두배이고 모든 값은 $2^{2k}$ 미만이므로 뭔가 절반으로 나누는 테크닉이 쓰일 것 같다고 유추할 수 있다.

처음 $k$ 개의 비트만 이용해서 구간합 배열을 만든다고 해보자.

$\oplus_{i=0}^x g_i$ 가 이미 등장했었다면 그 인덱스가 $y$ 라면 $[y+1,x]$ 구간은 $\oplus$합이 $0$이다.

$n=2^{k+1}$ 이고 $2^{k}$ 개의 수만 존재하기 때문에 이러한 구간은 최소 $2^k+1$ 개가 나온다.

왜냐면 처음 빈 구간은 $\oplus$합이 $0$ 인걸로 포함해 줬기 때문이다.

앞에 $2^k$ 개 까지 모두 다르다고 해도 비둘기 집의 원리에 의해 뒤에 $2^k$ 는 항상 적어도 하나랑 얻어걸리고 앞에서 $2^k$ 개 중에 $0$ 인 것이 하나 있어야 해서 $2^k+1$ 개가 나오는 것이다.

그럼이제 이러한 구간들이 최소 $2^{k}+1$ 개이므로, 이 구간들을 가지고 처음 $k$ 개의 비트를 제외한 뒤에 $k$ 개의 비트만 고려한다.

이 구간들은 $xor$ 합이 앞에 $k$개는 $0$ 이 나오기 때문에 뒤만 고려하게 된 것이다.

그럼 이제 또 $2^{k}+1$ 개이기 때문에 비둘기집 원리로 또 뒤에 $k$개의 비트만 봤을 때도 동일한 것이 생긴다.

그 두 구간이 disjoint하면 그게 정답이고 그렇지 않다면 겹치는 부분을 두 구간에서 모두 제외한 것이 정답이다.

후자의 경우 항상 겹치는 구간을 제거해도 구간의 길이가 남냐가 의문일 수 있는데, 처음 $2^{k+1}$개의 구간을 구하는 과정을 보면 구간들의 $s, e$ 가 모두 다름을 알 수 있다.

$e$ 는 원래 하나의 인덱스당 하나의 구간만 만들어지기 때문에 모두 다르고 $s$ 는 구간을 만드는 과정에서 현재 $\oplus$ 구간합 값의 인덱스를 현재로 덮어씌워주는 방식으로 해결한다.

$s_1=s_2$ 인 구간이 되려면 $e_1 + 1 \sim e_2$ 까지의 $\oplus$이 모두 같다는건데, 그럼 $e_1 +1 \sim e_2$ 까지의 구간이 만들어졌어야 했으므로 모순이다.

void solve() {
   int k;
   cin >> k;
   int n = 1 << (k + 1);
   vi g(n + 1);
   fv1(g);
   vi bit_idx(1 << k, -1);
   bit_idx[0] = 0;
   vector<pi> bit_seg(1 << k, {-1, -1});
   for (int i = 2; i <= n; i++) g[i] ^= g[i - 1];
   for (int i = 1; i <= n; i++) {
      if (bit_idx[g[i] >> k] != -1) {

         // new segment
         int s = bit_idx[g[i] >> k] + 1, e = i;

         int other_bits = g[e] ^ g[s - 1];
         if (bit_seg[other_bits].fi == -1) {
            bit_seg[other_bits] = {s, e};
         } else {
            auto [s2, e2] = bit_seg[other_bits];
            if (s2 > e || e2 < s) {
               cout << s2 << ' ' << e2 << ' ' << s << ' ' << e << endl;
            } else {

               cout << min(s, s2) << ' ' << max(s2, s) - 1 << ' ' << e2 + 1 << ' ' << e << endl;
            }
            return;
         }
      }
      bit_idx[g[i] >> k] = i;
   }
}

F. Doctor’s Brown HypothesisPermalink

F. Doctor’s Brown Hypothesis