Codeforces Round 875 (Div. 2)
A. Twin Permutations
$b_i=n+1-a_i$ 로 두면 모든 수를 같게 만들 수 있다.
B. Array merging
정답은 $a_i$ 에서 연속된 $k$ 들과 $b_i$ 에서 $k$ 를 최대로 많이 써줄 수 있는 횟수이다.
혹은 $b_i$에서 연속된 $k$들과 $a_i$ 에서 $k$를 최대로 많이 써줄 수 있는 횟수이다.
C. Copil Copac Draws Trees
BFS를 돌리는데 간선의 가중치를 이전에 거쳐온 간선보다 현재 간선이 더 인덱스가 적다면 한 바퀴를 돌아야 하므로 $+1$ 로 주고, 아니라면 $0$ 으로줘서 최단경로중 가장 큰 것이 정답이다.
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 Strings
E. Hyperregular Bracket Strings
Comments