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, 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해서 시도하면 된다.
바닥을 모르고 떨어지고 있다. 사실 이전 포스트 사이에 참여한 라운드가 좀 있지만 엄청나게 망하고 멘탈이 다 갈려버려서 후기도 못썼다. 정신 좀 차려보자.
A. Odd Set
길이가 2n인 수열에서 적절히 원소를 둘씩 짝지어 각 쌍들이 모두 홀수가 되도록 할 수 있는지 확인하는 문제. 두 자연수의 합이 홀수가 되려면, 홀수+짝수 형태야 한다. 따라서 수열 내에서 홀수의 개수와 짝수의 개수를 세서 같으면 Yes 다르면 No이다.
B. Plus and Multiply (업솔빙)
첫 번째 연산인 x * a는, 두 번째 연산 x + b로 치환될 수 있다. b = x*k (k는 자연수) 이라면 a = k+1인 x * a 연산과 동일하다. 따라서 첫 번째 연산을 적당히 하고 n까지 두 번째 연산을 적용하면 된다. 여기서 첫 번째 연산을 할 때마다 x가 a씩 증가하므로, 최대 log_a(n) 번 연산한다. 두 번째 연산도 모듈러를 통해 O(1)에 가능하다. 최종적으로 O(log n)에 가능하다.
첫 번째 연산과 두 번째 연산이 서로 치환될 수 있지 않을까 하는 경험에 근거한 의심을 금방 떠올렸지만 예시 입력을 잘못 계산하면서 모든게 꼬여버렸다.
C. Strange Function (업솔빙)
f(x)의 값을 고정하고 x가 어떤 수여야 하는지 관찰해보면 다음과 같은 규칙을 찾을 수 있다.
어떤 x가 f(x) = 2이려면, 1의 배수이면서 2의 배수가 아니어야 한다. 즉, x | lcm(1) 이다.
어떤 x가 f(x) = 3이려면, 1의 배수이면서 2의 배수이면서 3의 배수가 아니어야 한다. 즉, x | lcm(1, 2) 이다.
어떤 x가 f(x) = 4이려면, 1의 배수이면서 2의 배수이면서 3의 배수이면서 4의 배수가 아니어야 한다. 즉, x | lcm(1, 2, 3) 이다.
...
어떤 x가 f(x) = k이려면, 1의 배수이면서 ... k-1의 배수이면서 k의 배수가 아니어야 한다. 즉, x | lcm(1, 2, ... , k-1) 이다.
따라서 n 이하의 수 중 f(x) = k인 수의 개수는 ⌊ n / lcm(1, ... , k-1) ⌋ 개이다.
한편, lcm(1, 2, ... , 37) > 1e16 이다. 따라서 37까지만 확인하면 된다.
주어진 수열의 길이를 n, 합을 x라 하고, 새로 추가한 수들의 개수를 m, 그 합을 k라고 하면 아래와 같은 식으로 표현할 수 있다.
x - n이 0 이하이면, m=1로 하고 k가 x-n-m이면 성립한다.
x - n이 0 초과이면, k=0로 하고 (즉, 새로 추가할 모든 원소를 0으로 하고) m을 x-n이면 성립한다.
따라서 x - n이 0 이하일 때 1개, 0 초과일 때, x-n개 추가하면 항상 성립한다.
B. Bad Boy
이동 거리는 맨하탄 거리라고 할 수 있다. 따라서 경로와 무관하게 이동 거리는 가장 먼 두 점이다.
그림에서처럼 (0, 0)과 (N, M)으로 하면 이동 거리를 최대로 할 수 있다.
C. Challenging Cliffs
일단 주어진 수열 h을 정렬한다. 첫 번째 조건인 |h_1 - h_n|이 최소가 되도록 하기 위해서, 수열을 순회하면서 인접한 원소끼리 차이가 가장 작은 원소 둘을 선택한다. 선택한 원소의 위치를 a, b라고 해보자.
두 번째로 h_i ≤ h_{i+1}인 위치가 최대한 많게 배치해보자. h_j, h_{j+1}, ... , h_n, h_1, h_2, ... , h_i 순서로 한다면 h_n과 h_1 한 번을 제외한 나머지 모든 경우가 조건을 만족하므로 최대이다. 여기서 만약 길이가 2일 경우에는 h_j > h_i 일 수 있다. 이러한 경우도 고려해보면 h_i, h_{j+1}, ... , h_n, h_1, h_2, ... , h_j 순서로 배치할 수 있다.
D. Deleting Divisors (업솔빙)
아직도 게임 쪽은 전혀 감이 없다. 해설을 보았으나 그만 정신이 혼미해졌다. dp로 100까지 돌려본 뒤, 규칙을 발견하였다. dp식은 다음과 같다. x의 약수 중, k != 0, k != x인 k에 대하여, dp[x][a] = !(dp[x - k_1][!a] && dp[x - k_2][!a] && ... && dp[x - k_n][!a])
n이 2의 홀수 제곱일 경우는 무조건 Bob이 승리, 그 외의 경우에는 홀수엔 Bob, 짝수엔 Alice가 승리한다.
E1. Erase and Extend (Easy Version)
사전 순 비교이므로 앞쪽의 문자가 무조건 우선이다. 따라서 두 번째 연산으로 복사해 나가기 전에, 일단 적절히 잘라내서 최적의 prefix를 만들어야 할 것이다.
길이가 1부터 n인 prefix를 만들고 복사해서 n개의 문자열들을 만든다. 입력이 충분히 작으므로, 이 문자열들을 전부 비교해보고 가장 작은 문자열을 찾아도 된다.
A와 B 사이 점선이 맨하탄 거리로 최단 거리임이 자명하다. 이때, 대각선이 적절히 있다면 빨간 점선 대신 빨간 실선을 타고 이동할 수 있다. 따라서 (전체 점선 길이) - (빨간 점선 길이) +(빨간 실선 길이) 가 답이다. 대각선을 활용할 수 없는 경우는 (1) A와 B로 이루어진 직사각형(초록)을 지나지 않는 경우와 (2) 대각선의 기울기와 진행 방향이 엇갈리는 경우이다.
1번은 대각선을 나타내는 방정식에 x, y를 적절히 대입해서 확인해보면 되고, 2번은 A―B의 위치 관계와 기울기를 비교해보면 된다.
허용 오차가 1e-9라 무서워서 long double 썼는데 끝나고 다시 내보니 double 써도 맞았다.
주어진 격자를 잘 파싱한 뒤, 24개의 성냥을 다 확인해보면 된다. (row % 3 == 0 && col % 3 == 1) 이면 가로로 놓인 성냥, (row % 3 == 1 && col % 3 == 0) 이면 세로로 놓인 성냥을 확인할 수 있다.
D. 신나는 분수 계산
https://www.acmicpc.net/problem/9215 pair<ll, ll> 등으로 분수를 관리해주면 된다. 나는 구조체로 만들어서 operator overloading을 했다. 입력이 분수 상태로 주어지므로, string으로 받고 콤마와 나눗셈기호를 토큰으로 파싱하자.
https://www.acmicpc.net/problem/6503 문자열 s에서 i부터 시작하는 m개의 서로 다른 글자를 가진 부분 문자열과 i+1부터 시작하는 m개의 서로 다른 글자를 가진 부분 문자열은 s_i를 제외하고 prefix가 겹친다. 따라서 이 부분을 window로 잡고 투포인터로 해결이 가능하다.
m개의 서로 다른 글자를 가진 문자열을 구간으로 잡고 투포인터를 돌리면 된다. 이때 가장 긴 구간의 길이가 답.
G. 대운하
https://www.acmicpc.net/problem/2350 Minimum spanning tree가 아니라 Maximum spanning tree를 구한다고 생각해보자. 가중치가 큰 순서대로 간선을 하나씩 그래프에 추가해보고, 추가한 간선에 의해 연결되는 경로가 있는지 확인한다.
간선의 개수가 최대 1e5이므로 그대로 구현하면 당연히 TLE지만, 우리가 알고 싶은 것은 가중치의 값에 대한 것이므로 가중치가 같은 간선을 그래프에 추가할 때마다 경로를 확인하지 않아도 된다. 즉, 가중치가 같은 간선들을 그룹지어 전부 추가한 뒤 한 번만 경로를 확인하면서 진행해도 괜찮다. 가중치는 최대 200이므로 시간 내에 해결할 수 있다.
먼저 d>1이면, 상위 d명이 d-1, d-2, ... , 1, 0점을 나눠 가지고 남은 사람들에게 0점씩 분배해주면 최소한의 점수만 사용해서 조건을 만족할 수 있다. 남은 p점은 1등에게 몰아줘버리자. 만약 이렇게 나눠주었는데도 p가 부족해지면 불가능한 경우이다.
d=1이면, 상위 k명이 같은 점수를 나눠 가져가야 한다. 이 k명에게 최대한 많은 점수를 분배해주면 각각 p/k점씩 분배될 것이다. 그리고 남은 n-k명의 사람들은 p%k점을 나눠 가져 간다. n-k=0인데 (나눠줄 사람이 더 없는데) p%k점이 남거나, p%k점을 n-k명에게 나눠주었는데 ceil (p%k)/(n-k) 이 p/k점보다 크다면(상위권보다 더 받아버린다면) 실패한다.
I. 목걸이 수열
https://www.acmicpc.net/problem/2070 그리디하게 가능한 긴 목걸이 수열을 찾아 나가면 된다. S_1부터 가장 긴 목걸이 수열을 그룹화하고, 남은 S_i부터 또 가장 긴 수열을 그룹화하고 ... 이런 식으로 찾아 나가면 조건에 만족한다.
조건 2) 가능한 가장 긴 목걸이 수열이므로, 더 합쳐서 목걸이 수열을 만들 수 없다.
조건 1) 목걸이 수열은 0*1* 꼴 또는 이들의 조합이다. 0을 기준으로 1이 어떻게 배치되어 있는지 생각해보자. 수열을 잘 회전해서 목걸이 수열이 작아지려면, prefix에 얼마나 많은 0이 배치될 수 있는지, 그리고 남은 부분에 1이 얼마나 적게 배치될 수 있는지에 달렸다. 조건1을 만족하지 않는 경우를 예를 들면, (011)(01111) 이런 형태가 있을 것이다. 즉, 앞쪽 수열이 뒤쪽 수열보다 작으면, 그 두 수열을 합쳐도 목걸이 수열이다. 따라서 조건2처럼 더 합쳐서 목걸이 수열을 선택한다.
J. 동전
https://www.acmicpc.net/problem/3363 12개의 동전을 {0, 0, ... , 1, ... , 0} 이렇게 대입하여 더 무거운 동전 하나를 만들어보고, 반대로 {1, 1, ... , 0, ... , 1} 이렇게 대입하여 더 가벼운 동전 하나를 만들어본 뒤, 주어진 수식에 직접 대입해서 계산해본다. 조건을 만족하는 상태가 2가지 이상이면 indefinite이고, 1가지 미만이면 impossible이다.
문제의 직사각형을 좌표평면으로 옮겨서 생각해보자. 가로길이 a와 세로 길이 b는 각각 x축, y축에 대응되고 대각선은 원점과 (a, b)를 잇는 선분으로 이해된다.
서로소인 a, b에 대하여 왼쪽 그림에 표현하였다. x 증가량에 대하여, y의 증가량이 1을 넘는 순간마다 새로운 정사각형(초록)이 소모하는 것을 관찰할 수 있다. 또한 x가 a만큼 증가하면서 1을 넘는 순간마다 새로운 정사각형(노랑)을 소모하는 것을 볼 수 있다.
따라서 이 경우, (정사각형의 개수) = a + b - 1 이다.
한편, 공약수가 있는 a와 b에 대하여도 생각해보자. 마찬가지로 x 증가량에 대하여 y의 증가량이 1을 넘는 순간마다 새로운 정사각형(초록)을 소모하나, a와 b의 공약수인 시점에는 정사각형의 내부를 지나치는 것이 아니라 꼭짓점을 지나간다.(파란 점)
이 때는 새로운 정사각형(초록)을 소모하지 않게 된다. 따라서 a와 b의 공약수가 나타나는 횟수만큼, 서로소인 경우보다 정사각형을 덜 소모하는 것이다.
따라서 이 경우, (정사각형의 개수) = a + b - gcd(a, b) 이다. a와 b가 서로소라면 gcd(a, b) = 1이므로, 같은 식으로 표현할 수 있다.
이렇게 하여 문제에서 주어진 f(R)을 a와 b로 표현할 수 있게 되었다. 문제에서 구해야 할 것은 f(R) = N을 만족하는 서로 다른 R의 개수이다. 방금 만든 식을 대입해서 다시 표현해보면, a + b - gcd(a, b) = N을 만족하는 서로 다른 a, b 쌍의 개수 (단, a <= b)를 구하면 된다.
gcd(a, b)를 g라고 하고, 양변을 g로 나눠보자. 여기서 a/g와 b/g는 서로소임을 관찰해낼 수 있다. 또한 두 정수 a/g와 b/g의 합에 정수 1을 뺀 값인 N/g 또한 정수라는 점을 관찰할 수 있다. 다시 한번 식을 정리해보면 a/g + b/g = N/g + 1 (단, a/g와 b/g는 서로소, a/g <= b/g)이다.
N/g가 정수이므로, g는 N의 약수이다. N의 모든 약수에 대하여 g를 고정하고 가능한 a/g와 b/g를 전부 세주면 된다. 그러면 N의 약수 g를 구하는데 O( sqN )이고, 각 g에 대하여 합이 N/g + 1인 두 서로소를 구하는데 O( g )이므로, 정리하면 O( N )이 된다. (g <= sqN)
도미노에 적힌 수를 정점, 도미노를 간선으로 하는 그래프로 모델링을 해 보면 이 문제는 그래프에서 서로 다른 오일러 회로의 개수를 세는 문제로 해석된다. 직접 다 세볼 수는 있겠지만, TLE가 날게 뻔하므로(답이 최대 2^64일 수도 있다), 잘 관찰해서 경우의 수를 계산해야 한다.
오일러 회로가 성립하려면 모든 정점의 차수가 짝수여야 한다. 즉, 오일러 경로를 따라 이동한다면 어떤 정점에 들어올 때 쓸 간선 하나와 나갈 때 쓸 간선 하나가 필요하다. 정점의 차수를 d라고 하면, 이 정점을 방문하는 횟수는 d/2번이다.
각 d/2번의 방문마다 들어올 때 쓸 간선 하나와 나갈 때 쓸 간선 하나를 골라야 한다. 이때, 오일러 경로가 아니라 오일러 회로를 구해야 하므로 오일러 경로를 역방향으로 도는 경우 즉, 들어올 때 쓸 간선으로 나가고 나갈 때 쓸 간선으로 들어오는 경우를 하나의 경우로 처리해야 한다. 따라서 첫 번째로 방문하면, 가능한 경우의 수는 dC2 이다. 두 번째로 방문하면, 이미 선택한 두 간선을 제외한 d-2C2이다.
이런 식으로 총 d/2번 방문한다. 여기서도 오일러 회로이므로 각 방문에서 선택한 간선들의 순서는 무의미하다. 따라서 (d/2)!로 나눈 (dC2 * d-2C2 * ... * 2C2) / (d/2)! 이 한 정점에서 선택할 수 있는 모든 경우의 수이다. 모든 정점에 대하여 이 경우의 수를 곱해주면 답이 된다.
d에 따른 경우의 수를 f(d)라고 하면, f(d)는 미리 전처리로 구해 둘 수 있는데, 잘 관찰해보면 다음과 같은 규칙을 찾을 수 있다.
팰린드롬 문자열의 양 끝에 같은 문자를 추가하면 팰린드롬 문자열이라는 점을 활용하자. dp[i][j] = i부터 j를 잇는 가장 짧은 팰린드롬 보행의 길이라고 정의해보자. 초기에는 인접한 두 정점에 대하여 간선 하나로 이루어진 길이가 1인 보행들 그리고 정점 하나를 기준으로 연결된 두 간선으로 이루어진 길이가 2인 보행들이 존재한다.
모든 i, j에 대하여 만약 dp[i][j]가 존재한다면 i에 연결된 간선들과 j에 연결된 간선들을 함께 살펴본다. i에 연결된 i'으로 가는 간선의 문자와 j에 연결된 j'으로 가는 간선의 문자가 같다면, dp[i'][j'] = min(dp[i'][j'], dp[i][j] + 2)로 정의할 수 있다.
0과 1이 연결될 때까지 즉, dp[0][1]이 존재할 때까지 반복하면 된다. O( N^2 * M )에 해결 가능하다.
실제 구현은 dp[i][j]가 존재하는 쌍 (i, j)를 큐에 넣어서 관리하였다. 이해를 돕기 위해, 예시 입력에 대한 그래프와 dp테이블을 아래 첨부한다. (사실 그려놓고 설명에 끼워 넣을 데를 모르겠어서 여기서 넣었다.)
