Codeforces Round 867 (Div. 3)

A. TubeTube Feed (800)Permalink

A. TubeTube Feed

지문이 좀 읽기 어려운데 결론적으로 ai≤t−ia_i \le t - i 인 것 중 가장 큰 bib_i 를 찾는 문제이다.

B. Karina and Array (800)Permalink

B. Karina and Array

정렬하고 가장 작은 것 두개의 곱이나 가장 큰 것 두개의 곱이 정답이다.

음수 * 음수 = 가장큰 양수가 될 수 있기 때문이다.

C. Bun Lover (800)Permalink

C. Bun Lover

에디토리얼은 다른 풀이를 갖지만, 내가 푼 풀이는 다음과 같다.

잘 살펴보면 dpn=dpn−1+1+2ndp_{n}=dp_{n-1} + 1 + 2n 이라는 점화식을 세울 수 있다.

dpn=dpn−1+1+2ndpn−1=dpn−2+1+2(n−1)⋮dp5=dp4+1+2⋅4‾dpn=dp4+(n−5+1)+2(4+5+⋯+n) \begin{aligned} dp_n=dp_{n-1}+1+2n\\ dp_{n-1}=dp_{n-2}+1+2(n-1)\\ \vdots\\ \underline{dp_5=dp_{4}+1+2 \cdot 4}\\ dp_n=dp_4+(n-5+1)+2(4 + 5 + \cdots + n) \end{aligned}

임을 알 수 있으므로 바로 계산해줄 수 있다.

D. Super-Permutation (1200)Permalink

D. Super-Permutation

n=1n=1 일땐 항상 가능하다.

nn이 짝수일 때 항상 만들 수 있는 방법은 다음과 같다.

n 1 n-2 3 n-4 5 n-6 ... 2 n-1

와 같이 구성하면 된다.

nn이 11이 아닌 홀수일 땐 불가능하다.

kk가 aa에서 nn이 있는 자리라고 하자. ak=na_k=n

bk=bk−1+ak=bk−1+n(modn)b_{k}=b_{k-1}+a_k=b_{k-1}+n \pmod n 이 되면

bk≡bk−1(modn)b_k \equiv b_{k-1} \pmod n 이 되기 때문에 nn은 aa에서 항상 첫 자리를 가지고 있다. 즉, b1≡0(modn)b_1 \equiv 0 \pmod n 이다.

홀수일 때를 보자.

∑i=1ni=n(n+1)2≡0(modn)\sum_{i=1}^n i = \dfrac {n(n+1)}2 \equiv 0 \pmod n 이다. bn=0b_n = 0 이란 뜻이고 b1=bn=0b_1=b_n=0 이 되어버렸으므로 불가능하다.

  
void solve() {  
   int n;  
   cin >> n;  
   if (n == 1) {  
      cout << 1 << endl;  
   } else if (n % 2 == 1) {  
      cout << -1 << endl;  
   } else {  
      vi ans(n + 1);  
      for (int i = 1; i <= n; i += 2) ans[i] = i;  
      for (int i = n; i >= 0; i -= 2) ans[n - i] = i;  
      for (int i = 0; i < n; i++) cout << ans[i] << ' ';  
      cout << endl;  
   }  
}

E. Making Anti-Palindromes (1600)Permalink

E. Making Anti-Palindromes

일단 홀수면 불가능하다.

동일한 알파벳이 n/2n/2 개보다 많으면 항상 si=sn−1−is_i=s_{n-1-i} 인 부분이 생기므로 불가능하다.

그렇지 않다고 하자.

si≠sn−1−is_i \ne s_{n-1-i} 인 쌍을 발견했을 때 sis_i와 sn−1−is_{n-1-i} 중 작은 알파벳의 개수를 세주자.

모든 알파벳의 세진 개수를 배열에 넣고 정렬한다. 이 배열을 xx 라 한다.

11번의 교체로 항상 si=sn−1−is_i = s_{n-1-i} 인 쌍을 두 개나 한 개를 제거할 수 있다.

최대한 두 개를 제거하는걸 많이 쓴 다음 한 개로 제거해야 하는 것을 제거해야 한다.

다음과 같이 쌍이 있다고 하자.

s=cbaaaaaabc
a - a
a - a
a - a
b - b
c - c

이 경우 정답은 33 인데 왜그런지 보자.

x=[3,1,1]x=\left[ 3,1,1 \right] 이 된다.

서로 다른 알파벳을 바꾸는 경우 항상 지워야 할 것이 22개씩 줄어든다. 가령 다음과 같다.

[3,1,1]→[2,1,0]→[1,0,0]\left[ 3,1,1 \right] \to \left[ 2,1,0 \right] \to \left[ 1,0,0 \right]

이제 나머지 aa 는 한 개 혼자 남았으므로 항상 11번의 스왑으로 한개만 삭제해줄 수 있다.

이런식으로 xx에서 가장 큰 수와 나머지 것들의 합을 비교하면 된다.

∑i=1n−1xi<x0\sum_{i=1}^{n-1} x_i < x_0 라면 정답은 x0x_0 이고, 그렇지 않다면 정답은 ⌈∑i=0n−1xi2⌉\left\lceil \dfrac {\sum_{i=0}^{n-1} x_i}2 \right\rceil 이다.

void solve() {
   int n;
   string s;
   cin >> n >> s;
   if (n % 2 == 1) {
      cout << -1 << endl;
      return;
   }
   vi cnt(26);
   for (char c: s) cnt[c - 'a']++;
   for (int i = 0; i < 26; i++) {
      if (cnt[i] > n / 2) {
         cout << -1 << endl;
         return;
      }
   }
   vi c(26);
   for (int i = 0; i < n / 2; i++) {
      if (s[i] == s[n - 1 - i]) {
         c[min(s[i], s[n - 1 - i]) - 'a']++;
      }
   }
   vi x;
   for (int i = 0; i < 26; i++) if (c[i]) x.pb(c[i]);
   sort(all(x));
   int sum = acc(x);
   if (sum == 0) {
      cout << 0 << endl;
      return;
   }
   int other = sum - x.back();
   if (x.back() > other) {
      cout << x.back() << endl;
   } else {
      cout << (sum + 1) / 2 << endl;
   }
}

F. Gardening Friends (1700)Permalink

F. Gardening Friends

전형적인 re-rooting 테크닉을 쓰는 문제여서 설명을 생략한다.

G1. Magic Triples (Easy Version) (1700)Permalink

G1. Magic Triples (Easy Version)

1≤ai≤1061 \le a_i \le 10^6 이므로 ai≤aj≤aka_i \le a_j \le a_k라 할 때, aka_k 은 ai⋅b2a_i \cdot b^2 이기 때문에 b2≤106b^2 \le 10^6 인 bb 까지만 검사를 해줄 수 있다.

수를 세는건 단순히 경우의 수를 세면 된다.

이는 시간복잡도 O(103⋅∑n)O(10^3 \cdot \sum n) 이 걸릴 것이다. 시간내에 충분히 통과 가능하다.

const int MAX = 1e6;
const int SQ = 1e3 + 100;
int cnt[MAX + 1];
void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
 
   for (int i = 0; i < n; i++) cnt[a[i]]++;
 
   ll ans = 0;
   for (int b = 1; b <= SQ; b++) {
      for (int i = 0; i < n; i++) {
         if (a[i] % (b * b) == 0) {
            if (i == n - 1 || a[i] != a[i + 1]) {
               if (b >= 2) {
                  int X = a[i] / b / b;
                  int Y = a[i] / b;
 
                  ans += 1ll * cnt[a[i]] * cnt[X] * cnt[Y];
               } else {
                  ans += 1ll * cnt[a[i]] * (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
               }
            }
         }
      }
   }
   cout << ans << endl;
   for (int i: a) cnt[i] = 0;
}

G2. Magic Triples (Hard Version) (2200)Permalink

스킵하려다가 에디토리얼을 보고 어떻게 푸는지 공부했다.

경우를 구간으로 나눠서 세는 테크닉은 특이해서 기억할만 했다.

G2. Magic Triples (Hard Version)

다음과 같은 경우를 순서대로 각각 세준다.

  • b=1b=1
  • aj≥M2/3a_j \ge M^{2/3} ⟹\Longrightarrow aj⋅b=ak≤M⟹b≤M1/3a_j \cdot b = a_k \le M \Longrightarrow b \le M^{1/3}
  • aj<M2/3a_j < M^{2/3}

각각 1,2,3 번이라고 하면

배열에 어떤 수가 몇개 있는지 판단하는 시간복잡도를 무시해서 O(1)O(1) 이라 할 때,

1번은 O(n)O(n)에 가능하고,

2번은 b≤M1/3b \le M^{1/3} 이고 aja_j 의 후보가 최대 nn개라서 O(n⋅M1/3)O(n \cdot M^{1/3}) 이면 된다.

3번은 ai⋅b=aja_i \cdot b = a_j 이기 때문에 bb의 후보를 11이 아닌 aja_j 의 약수로 제한할 수 있기 때문에 aj≤M2/3a_j \le M^{2/3} 이고 약수들은 O(X)O(\sqrt{X}) 로 찾을 수 있어서 결국 aj≤M2/3a_j \le M^{2/3} 인 aja_j는 많아봤자 nn개이기 때문에 O(n⋅M1/3)O(n \cdot M^{1/3}) 에 해결된다.

따라서 O(n⋅M1/3⋅α)O(n \cdot M^{1/3} \cdot \alpha) 에 모두 검사할 수 있고, 해결 가능하다.

α\alpha는 배열에 어떤 수가 몇개있는지 세는 시간복잡도이다. O(log⁡N)O(\log N)이 될 것이다.

const int MAX = 1e9;  
  
void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   sort(all(a));  
  
   auto cnt = [&](int x) {  
      return ubi(a, x) - lbi(a, x);  
   };  
  
   ll ans = 0;  
   for (int i = 0; i < n; i++) {  
      if (i == n - 1 || a[i] != a[i + 1]) {  
         ll c = cnt(a[i]);  
         ans += c * (c - 1) * (c - 2);  
      }  
   }  
  
   auto count = [&](ll aj, int b) -> ll {  
      if (aj % b) return 0;  
      int x = aj / b;  
      ll z = aj * b;  
      if (z > MAX) return 0;  
  
      int xc = cnt(x);  
      if (!xc) return 0;  
      int zc = cnt(z);  
  
      return 1ll * xc * zc;  
   };  
  
   for (int i = 0; i < n; i++) {  
      if (a[i] >= 1e6) {  
         for (int b = 2; b <= 1e3; b++) {  
            ans += count(a[i], b);  
         }  
      } else {  
         for (int b = 1; b * b <= a[i]; b++) {  
            if (a[i] % b == 0) {  
  
               if (b != 1) {  
                  ans += count(a[i], b);  
               }  
  
               int b2 = a[i] / b;  
               if (b2 != b && b2 != 1) {  
                  ans += count(a[i], b2);  
               }  
            }  
         }  
      }  
   }  
   cout << ans << endl;  
}

Comments

You may also enjoy