ABC353

C. Sigma Problem (795)

이분 탐색으로 1억 이상이 되는 쌍의 개수를 모두 찾은 다음,
누적 합을 통해 시그마 2개를 빠르게 계산해 줍니다.

ABC352

D. Permutation Subsequence (714)

인덱스와 함께 정렬하면 끝입니다.

E. Clique Connect (1030)

크루스칼 알고리즘의 작동 방식에 의해 완전 그래프가 아닌, 간선을 조금만 이어줘도 됩니다.

F. Estimate Order (2052)

퍼즐 맞추기처럼 bit dp를 수행하면 됩니다.

ABC351

D. Grid and Magnet (974)

자석과 인접한 칸들을 x라 합시다.
x가 아닌 연결성분들의 크기와, 그 주변에 있는 x의 수를 더한 값의 최댓값이 답입니다.

ABC350

D. New Friends (773)

연결성분에서의 완전 그래프 만들기와 같습니다.
연결 성분에서의 정점의 개수를 $N$개라 하면, $\frac{N(N-1)}{2}$에서 원래 있던 간선들을 빼 주면 됩니다.

G. Mediator (2058)

dsu로 부모 배열을 확인하면서 온라인으로 처리하면 되는데, 연결 성분을 합칠 때 smaller to larger을 사용하여 시간 복잡도를 줄여야 합니다. 또한 합쳐지는 연결 성분을 dfs로 순회하여 루트를 바꾸어 주어야 합니다.

ABC349

D. Divide Interval (832)

S는 세그트리의 정점에 대응됩니다.
구현을 쉽게 하려면 l과 r이 홀수일 때 구간을 추가하고, 매번 2로 나눕니다.

ABC348

D. Medicines on Grid (1108)

약들을 정점으로 가지는 그래프를 만들면 끝입니다. (그래프 구성하기)

ABC347

C. Ideal Holidays (926)

a+b를 w라 합시다. 모든 날짜를 w로 나눈 나머지로 변경합니다.
날짜를 두 번 이어붙여, 구간을 잘 잡아줍니다.

D. Popcount and XOR (1041)

C의 비트가 0인 경우에는 1의 개수가 0, 2가 될 수 있습니다.
C의 비트가 1인 경우에는 1의 개수는 1밖에 될 수 없습니다.

이 관찰을 바탕으로 1들을 배분하면 됩니다. -1이 되는 경우에 각별히 주의해야 합니다.

E. Set Add Query (1166)

S의 크기를 담은 배열의 구간 합이 답이 됩니다. (누적 합)

ABC346

D. Gomamayo Sequence (845)

11, 00과 같이 붙어있는 것으로 순회하면 됩니다.
S의 홀수번째 비트를 반전시키는 테크닉을 쓰면 시간 복잡도를 줄일 수 있습니다.

E. Paint (1053)

거꾸로 생각하면 쉽습니다.

ABC344

D. String Bags (854)

dp[i][j] = i번째 bag까지 봤을 때, T의 j번째 문자까지 만드는 비용의 최솟값