KimHwon

요즘 컨디션이 좋다. 실력이 늘은건지 웰노운이 나온건지 잘 모르겠지만 암튼 계속 올라서 좋긴 하다.

A. Balanced Substring

a의 개수와 b의 개수가 같은 substring을 찾는 문제이다. 문자열 "ab" 또는 "ba"는 항상 조건에 맞기 때문에, 그냥 주어진 문자열에서 "ab" 또는 "ba"가 있는지만 판별하면 된다.

놀랍게도 완탐을 돌리다 TLE 맞고 틀렸다. n이 작길래 무지성으로 냈는데 다시 찬찬히 계산해보니 1e9가 넘더라

B. Chess Tournament

참여자들을 정점으로 하는 그래프로 모델링하면 완전 그래프가 만들어진다. 1번 타입의 참가자는 절대 지면 안된다. 따라서 1번 타입 참가자에 연결된 간선들을 모두 지운다. 이제 남은 간선들을 가지고 2번 타입 참가자들을 연결해보자. 2번 타입 참가자들은 최소 1번만 이기면 된다. 즉, outdegree가 1 이상이 되도록 만들어야 한다. 완전 그래프기 때문에, 항상 2번 타입 참가자들을 잇는 단순 사이클이 만들어 질 수 있다. 아래 그림은 세 번째 테스트케이스의 풀이이다.

단순 사이클이 만들어지지 않는 경우는, 2번 타입 참가자가 2명 이하인 경우이다. 한편 2번 타입 참가자가 0명이라면 모든 참가자들이 서로 비기기만 하면 된다.(첫 번째 테스트케이스) 따라서 2번 타입 참가자가 1명이나 2명인 경우만 NO이고 나머지 모든 경우는 YES이다. YES라면, 앞에서 설명한 대로 단순 사이클을 만들고 그 사이클에 포함되는 간선을 제외한 모든 간선을 비기는 경우로 지정하면 된다.

C. Jury Meeting

nice하지 않은 경우를 생각해보자. 문제에 제시된 예시들을 잘 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

• 수열 $a$에서 가장 큰 원소를 $a_k$라고 하자. $a_k$와 값이 같은 원소가 더 있다면, 항상 nice하다.
• 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다.
• $a_k$ 이후에 값이 $a_k - 1$인 원소가 하나도 없다면 항상 nice하지 않다. 즉, $p$에 따라 $a$를 재배열했을 때, 구간 (k, n] 안의 모든 $i$에 대하여 $a_i < a_k - 1$이면 항상 nice하지 않다.

첫 번째 경우는 항상 nice하므로 $n!$이 답이다. 두 번째 경우는 항상 nice하지 않으므로 0이 답이다. 세 번째 경우를 잘 계산해야 하는데, 값이 $a_k - 2$보다 작은 원소가 $l$개라고 하면 다음과 같이 계산할 수 있다. $$ n! - \sum_{i=0}^l (n-i-1)! {k \choose i} i! $$ 팩토리얼은 오프라인으로 미리 계산해 둘 수 있고, combination은 페르마의 소정리와 분할정복을 통해 O(log n)에 계산할 수 있다.

역시 조합론 문제는 어렵다. 예제가 굉장히 잘 나와있어서 겨우 규칙을 관찰해 낼 수 있었다.

D. Inconvenient Pairs

불편한 쌍이 만들어지는 조건은 다음과 같다.

• 교차로 위에 있는 사람은 항상 불편한 쌍을 만들 수 없다.
• 같은 열에 있는 가로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.
• 같은 행에 있는 세로 도로에 있으면서 서로 다른 도로에 있는 두 사람은 항상 불편한 쌍이다.

먼저, 세로 도로와 사람들을 x좌표에 대하여 정렬한다. 이를 스위핑하면 같은 열에 있는 사람들을 골라낼 수 있다. 예를 들어 두 번째 테스트 케이스에서 1, 6, 7번 사람이 한 그룹, 8번 사람이 다른 한 그룹으로 분류된다. 이 골라낸 그룹을 이번엔 y좌표로 정렬한다. 그러면 한 그룹 내에서 같은 가로 도로에 있는 사람의 수를 찾아낼 수 있다. 현재 그룹의 크기를 $n$이고 같은 도로에 있는 사람이 $k$명이면 $\frac{\sum k(n-k)}{2}$이 불편한 쌍의 개수다.

같은 방식으로 y좌표에 대하여 한 번 더 하면 된다.

역대급 퍼포먼스다. 원래 carrot은 잘라내고 캡쳐해오는데 오늘은 좀 자랑하고 싶어서 다 나오게 찍었다.

A. Domino Disaster

입력된 문자열의 각 문자에 따라 출력할 문자가 1대1로 대응된다. U이면 D, L이면 L, R이면 R로 대응해서 출력하면 된다.

B. MEXor Mixup

MEX 결과가 a라는 것은, [0, a) 범위의 모든 정수가 이미 수열 내에 존재한다는 뜻이다. 오프라인으로 일단 0~3e5 까지 xor한 결과를 저장해 둔다. a-1까지 xor한 결과를 가지고 b와 비교해볼 수 있다. 만약 $xored[a-1] = b$라면 a가 답이다. $xored[a-1] \ne b$ 라면 $xored[a-1] \oplus b$을 추가하면 b가 나오기 때문에 a+1이 답이다. 그런데 $xored[a-1] \oplus b$가 a와 같을 수 있다. 그렇다면 임의의 x에 대하여 $xored[a-1] \oplus b \oplus x$와 $x$를 수열에 추가하면 된다. 이 때 답은 a+2이다.

C. Carrying Conundrum

brute force로 해결될 수도 있을 것 같은데, 그냥 무지성 경우의 수 DP를 사용했다.

$dp[i][bit] = (i\text{번째 자리까지 덧셈을 했을때, 자리올림이 }bit)$으로 정의한다. 자리 올림을 2bit로 들고 다니면서 관리해주고, 1의 자리부터 1e9의 자리까지 처리해주면 된다. 이 때, (0, n), (n, 0)인 순서쌍도 세지므로 dp 결과에 -2를 하면 답이다.

E. Non-Decreasing Dilemma

아주 전형적인 세그먼트 트리 문제이다. 흔히 알려진 테크닉인 금광세그를 풀어봤다면 쉽게 풀이를 떠올렸을 것이다.

세그먼트 트리의 노드를 다음과 같은 6개의 원소를 가진 struct로 정의하자.

• ans : 이 구간에서 단조증가하는 subarray의 개수. 즉, 구간쿼리의 답
• sz : 이 구간의 길이
• lval : 이 구간의 왼쪽 끝 원소의 값
• lsz : 이 구간의 왼쪽 끝 원소를 포함하는 subarray의 길이
• rval : 이 구간의 오른쪽 끝 원소의 값
• rsz : 이 구간의 오른쪽 끝 원소를 포함하는 subarray의 길이

일단 트리의 leaf에서는 ans = 1이고, lval = rval, sz = lsz = rsz이다.

두 서브노드 left와 right가 합쳐질 때 위 그림과 같이 두 가지 경우가 존재할 수 있다. 그림에서 초록색 박스는 left 노드, 파란색 박스는 right 노드이다. 노란색은 각 노드가 커버하는 구간에서 subarray이다.

첫 번째로 $left.rval > right.lval$인 경우이다.(빨강색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 그대로 나열된다. 따라서, $ret.ans = left.ans + right.ans$이다.

두 번째로 $left.rval \leq right.lval$인 경우이다.(하늘색 박스) 이 때, left의 오른쪽 끝 subarray(노란색 r) 과 right의 왼쪽 끝 subarray(노란색 l)은 merge된다. 즉, 이전에 존재했던 두 subarray를 제외하고, 새로 생긴 subarray(노란색 r+l)을 계산해야 한다. 따라서, $ret.ans = left.ans + right.ans - \frac{left.rsz(left.rsz+1)}{2} - \frac{right.lsz(right.lsz+1)}{2} + \frac{(left.rsz+right.lsz)(left.rsz+right.lsz+1)}{2}$이다.

단, 여기서 주의해야 할 것은, 서브노드 전체가 하나의 subarray로 존재하는 경우에는 ret.lsz 또는 ret.rsz를 다시 계산해야 한다. 예를 들어 위 그림처럼 $left.lsz = left.sz$인 경우, ret.lsz는 left.lsz가 아니라 left.sz + right.lsz이다. 마찬가지로 $right.lsz = right.sz$인 경우, $ret.rsz = left.rsz + right.sz$이다.

이러한 방식으로 두 서브노드를 합칠 수 있다. 세그먼트 트리를 정의했다면 나머지는 각 쿼리에 맞게 트리에 update 또는 query를 하면 된다.

대박났다. carrot에서 퍼플 퍼포먼스 찍힘 :blobhappy:

A. Digits Sum

interesting하지 않은 수는 맨 마지막 자리가 9인 수이다. 따라서 $\frac{(n+1)}{10}$이 답이다.

B. Reverse String

첫 번째로 주어진 문자열을 적절히 '접어서' 두 번째 문자열로 만들 수 있는지 확인하는 문제이다. 문자열의 길이가 500 이하로 매우 작으므로, '접는' 중심을 하나씩 잡아보면서 확인해볼 수 있다.

C. Penalty

페널티킥을 10번 할 때, 최대한 빨리 승패가 결정나는 횟수를 찾는 문제이다.

가능한 빨리 승패가 나는 경우로 첫 번째 팀이 최대한 많이 넣고 두 번째 팀이 최대한 적게 넣도록 ?를 채운 경우와, 첫 번째 팀이 최대한 적게 넣고 두 번째 팀이 최대한 많이 넣도록 ?를 채운 경우 두 가지를 확인해보면 된다. 각 경우에 대하여 남은 기회가 점수차보다 작아지면 승패가 결정난다. s의 길이가 10이므로 직접 시뮬레이션하면서 알아낼 수 있다.

D. Backspace

어떤 키 대신 backspace를 누른다면 그 키에 해당하는 알파벳 하나가 사라지고, 그 알파벳의 바로 앞의 문자가 지워진다. 즉, 연속한 2개의 문자를 지워서 주어진 문자열로 만들 수 있는지 확인하면 된다. 앞에서부터 순회하면서 그리디하게 진행하면 된다.

A번이 약간 말려서 당황했는데, 그래도 B, C가 잘 풀려서 다행이었다. 4솔도 노려볼 만했는데 더 풀지는 못해서 아쉽다.

A. AquaMoon and Two Arrays

두 수열이 주어지고 한 수열에 적절히 연산을 하여 두 수열이 같게 만들어야 한다. 일단, 연산을 해도 각 수열의 합은 보존되므로 두 수열의 합이 다르다면 무조건 불가능하다. 두 수열의 각 원소의 차를 구하고, 그 차가 0 초과인 원소를 0 미만인 원소에 옮겨주면 된다.

B. AquaMoon and Stolen String

n개의 문자열에서 한 개의 문자열을 없앤 뒤 남은 n-1개의 문자열을 섞는다. 이 때 없어진 문자열을 찾는 문제이다.n-1개의 문자열을 섞을 때 같은 열의 두 원소 즉, 문자열 S와 T가 있다면$S_i$ 와 $T_i$를 바꾼다. 따라서 각 열에 대하여 알파벳의 등장 횟수는 보존된다. 초기상태인 n개의 문자열에 대하여 각 열에 등장하는 알파벳의 수를 계산해두고, 섞인 n-1개의 문자열이 주어졌을 때, 각 열에 해당하는 알파벳의 수를 계산하면 사라진 알파벳 한 개를 찾을 수 있다.인터랙티브 문제인데 왜 인터랙티브인지 모르겠다.

C. AquaMoon and Strange Sort

버블정렬의 특성을 활용한 문제이다. 주어진 수열이 정렬되었을 때, 모든 원소가 처음 위치에서 이동한 거리가 짝수가 되어야 한다. 같은 수가 등장할 수 있기 때문에 이들을 적절히 재배치하는 것이 관건이다.

map을 사용하여 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 각각 센다. 정렬 한 후에 다시 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 센다. 두 상태에서 센 수가 같다면 ok이다. 이는 짝수 번째 위치에서 다시 짝수 번째 위치로 이동하고, 홀수 번째 위치에서 다시 홀수 번째 위치로 이동했기 때문에 조건을 만족한다. 반대로 두 상태에서 센 수가 다르다면 짝수 번째 위치에서 홀수 번째 위치로 이동하거나, 홀수 번째 위치에서 짝수 번째 위치로 이동한 수가 있다는 뜻이므로 불가능한 경우이다.

컨디션이 다시 올라왔고 잘 풀어서 기분이 좋다.

A. Exciting Bets

두 음이 아닌 정수 a, b가 주어졌을 때 적절한 연산을 하여 gcd(a, b)를 최대로 하는 문제이다. 먼저, 문제에 제시된 대로 0, 0이라면 INF라고 하니 $a = b$인 경우는 0, 0으로 만들면 될 것이다. $a \ne b$인 경우, $gcd(|a-b|, 0)$ 인 상태가 최대이다.

이는 $gcd(a, b) = gcd(a-b, b)$임을 통해 확인할 수 있다. 라운드 중에는 위의 등식이 생각나지 않아서 직접 예제를 만들어보다 보니 우연찮게 발견했다. 맞았으니 다행이긴 한데 많이 아쉬웠던 풀이.

B. Customising the Track

수열이 주어졌을 때 $\sum_{i=1}^n \sum_{j=i+1}^n | a_i - a_j |$이 최소가 되도록 적절히 연산을 하는 문제이다. 연산을 했을 때 수열의 원소의 합은 보존되기 때문에, 수열의 원소들에 최대한 균등하게 분배할 때가 최선이다. 따라서 n-reminder개의 sum/n과, reminder개의 sum/n+1가 구성된다.

C. Need for Pink Slips

$0.1 \leq v$이므로 c, m, p에 대하여 각각 최대 10번씩 밖에 선택되지 않는다. 따라서 완전탐색으로 모든 경우를 확인해볼 수 있다. 풀이 자체는 매우 쉬운데, 실수오차를 잘 핸들링하는 것을 의도한 문제 같다.

D1. RPD and Rap Sheet (Easy Version)

Easy version의 k=2 조건에서는 bitwise XOR과 동일하다. 1부터 n-1까지 모두 한 번씩 시도해 볼 수 있다. xor은 교환법칙과 결합법칙이 성립하므로, 이전에 시도해 본 값을 모두 xor해서 들고 다니다가 현재 시도할 값과 xor해서 시도하면 된다.