Codeforces Round 875 (Div. 2)

A. Twin PermutationsPermalink

A. Twin Permutations

$b_i=n+1-a_i$ 로 두면 모든 수를 같게 만들 수 있다.

B. Array mergingPermalink

B. Array merging

정답은 $a_i$ 에서 연속된 $k$ 들과 $b_i$ 에서 $k$ 를 최대로 많이 써줄 수 있는 횟수이다.

혹은 $b_i$에서 연속된 $k$들과 $a_i$ 에서 $k$를 최대로 많이 써줄 수 있는 횟수이다.

C. Copil Copac Draws TreesPermalink

C. Copil Copac Draws Trees

BFS를 돌리는데 간선의 가중치를 이전에 거쳐온 간선보다 현재 간선이 더 인덱스가 적다면 한 바퀴를 돌아야 하므로 $+1$ 로 주고, 아니라면 $0$ 으로줘서 최단경로중 가장 큰 것이 정답이다.

D. The BOSS Can Count PairsPermalink

D. The BOSS Can Count Pairs

$a_i \cdot a_j = b_i+b_j \le 2n$ 이기 때문에 $\text{Min}(a_i,a_j) \le \sqrt{ 2n }$이다. $S=\sqrt{ 2n }$이라고 하자.

$cnt(x,y)$를 $a_i=x,b_i=y$ 인 것의 개수라고 두자, $x \le S$ 인 경우만 저장해둔다.

따라서 map을 안쓰고 배열로 가능하다.

$a_i=a_j$ 인경우를 세면,

$\dfrac{\displaystyle \sum_{i=0}^{n-1}cnt(a_i,a_i^2-b_i)-\sum_{s=1}^{S}cnt(s,s^2/2)}{2}$ 이다.

모든 쌍에 대해 세준 후, $i=j$ 인 경우를 빼주고 $i<j$ 를 맞추기 위해 $2$로 나눠준 것이다.

이제 $a_i \neq a_j$ 인 경우를 세며, $i<j$ 란 조건을 $a_i<a_j$ 로 바꿔도 무방하다.

$\text{Min}(a_i, a_j) \le S$ 이기 때문에 $\displaystyle \sum_{j=0}^{n-1} \sum_{a_i=1}^{\text{Min}(a_j-1,\left\lfloor 2n/a_j \right\rfloor)}cnt(a_i,a_i \cdot a_j-b_i)$ 를 세줄 수 있다.

$a_i \le S$여서 $O(n \sqrt{ n })$ 으 시간복잡도가 나온다.

루트질을 할 생각은 했는데, $a_i=a_j$ 인 경우를 따로 세준다음 빠르게 세줄 수 있는 것을 놓쳤다.

const int MAX = 2e5 + 5;  
int a[MAX], b[MAX], cnt[640][MAX];  
void solve() {  
   int n;  
   cin >> n;  
   int S = sqrt(n * 2);  
   for (int i = 0; i < n; i++) cin >> a[i];  
   for (int i = 0; i < n; i++) cin >> b[i];  
   for (int i = 0; i < n; i++) if (a[i] <= S) cnt[a[i]][b[i]]++;  
   ll ans = 0;  
   for (int i = 0; i < n; i++) {  
      if (a[i] <= S) {  
         if (a[i] * a[i] - b[i] >= 0 && a[i] * a[i] - b[i] <= n)  
            ans += cnt[a[i]][a[i] * a[i] - b[i]];  
      }  
   }  
   for (int s = 2; s <= S; s += 2) ans -= cnt[s][s * s / 2];  
   ans /= 2;  
   for (int i = 0; i < n; i++) {  
      for (int jv = 1; jv <= min(a[i] - 1, 2 * n / a[i]); jv++) {  
         assert(jv <= S);  
         if (jv * a[i] - b[i] >= 0 && jv * a[i] - b[i] <= n)  
            ans += cnt[jv][jv * a[i] - b[i]];  
      }  
   }  
   cout << ans << endl;  
   for (int i = 1; i <= n; i++) for (int j = 1; j <= S; j++) cnt[j][i] = 0;  
}

E. Hyperregular Bracket StringsPermalink

E. Hyperregular Bracket Strings

F. Mex TreePermalink

F. Mex Tree