주어진 수열의 길이를 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개의 문자열들을 만든다. 입력이 충분히 작으므로, 이 문자열들을 전부 비교해보고 가장 작은 문자열을 찾아도 된다.
pElements로 받아온 원소의 포인터를 그대로 pData에 복사한 뒤, 여기에 Write 또는 EnsureRead로 bit-wise read/write를 하고 있다. 만약 원소가 기본 데이터 타입(int, TCHAR 등)이면 큰 문제 없이 동작하겠지만 class라면, 특히 멤버로 또다른 class나 collection을 가지고 있다면 이와 같은 문제가 생길 수 있다.
원소의 멤버로 있는 값이 포인터를 가지고 있다면, 이 포인터 값도 함께 직렬화된다. 불러오기를 통해 가져온 포인터 값은, 현재 runtime 중인 프로세스가 가지고 있는 heap이 아니라, 이전에 저장했던 프로세스가 가지고 있는 heap을 가리키고 있는 포인터일 것이다. 따라서 잘못된 위치를 가리키는 포인터를 사용하여 _CrtisValidHeapPointer exception이 발생한다.
이를 해결하기 위해서는 다음과 같이 SerializeElements를 오버로딩하면 된다.
template<>
void AFXAPI SerializeElements(CArchive& ar, MyClass* pElements, INT_PTR nCount)
{
// Do what you want.
}
또는 그냥 Serialize메서드를 호출하지 말고, 반복문 등을 사용해서 모든 원소를 직접 ar 객체에 << 또는 >>연산자로 써 주면 된다.
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테이블을 아래 첨부한다. (사실 그려놓고 설명에 끼워 넣을 데를 모르겠어서 여기서 넣었다.)
문제에서 정의한 2050-number를 잘 관찰해 보면 a * 2050*10^b + c *2050*10^d + ... 이고 여기서 2050을 묶어내면 2050 * (a*10^b + c*10^d + ...)이다. 즉, 2050에 임의의 자연수가 곱해진 모양이므로 주어진 수를 2050으로 나눠보면 된다.
B. Morning Jogging
체크포인트 사이 경로들의 최솟값을 관리해주면 된다. 일단 수열 b_i를 정렬하자. i번째 체크 포인트까지 잘 도착했다고 해보자. i+1번째 체크포인트에 가는 경로들 b_ij를 잘 배분해서 최소가 되게 만들어줘야 할 것이다. 현재까지 각 경로의 최솟값(i번째 체크포인트까지 왔을 때 각 runner의 tiredness)을 t_j라고 하면, t의 각 원소들을 가능한 최소로 만드는게 최적이다. 따라서 pair(t, j)를 내림차순으로 정렬하고, 가장 큰 t_j에 b_i+1중 가장 큰 원소를 매칭해주자. 이 과정을 2차원벡터 등에 잘 저장해서 trace해주면 된다.
C. Fillomino 2
주대각선에 있는 숫자만큼 계단 모양을 인접하게 색칠해야 한다. 일단 주대각선에 있는 숫자들이 permutation이고 합이 계단 모양에 있는 칸 수와 같으므로 다 칠할 수 있다고 합리적 의심을 해보자. 만약에 (i, i)에 있는 수로 (i-1, i-1)을 방해하려면 i-1줄 이상으로 올라가야 한다. 그런데 i+1줄까지 가장 많이 칠해진 경우는 N, N-1, N-2, ... 만큼 칠해진 경우일 것이며 i+1줄까지 계단 모양의 칸 수 또한 N, N-1, N-2, ... 으로 서로 같다. 즉, 항상 자신과 같은 줄이나 그 아래 줄만 사용해서 모두 색칠할 수 있다. 따라서 최대한 아래쪽으로 붙여서 칠해나가면 항상 색칠이 가능하다.
D. Explorer Space (업솔빙)
역시나 DP가 발목을 잡는다. 1시간반이나 붙잡고 있었는데 다익스트라를 사용한 풀이로 풀다가 망했다. dichoy27의 풀이는 이러하다. 일단 갔다 와야되니까 K가 홀수일때는 항상 불가능하다. 그리고 오는 길 가는 길 똑같으니까 K/2번 가는 것만 생각하면 된다. dp[i][j][d] = (i, j)위치에서 d만큼 이동했을 때 최솟값이라 하면, dp[i][j][d] = min(dp[i][j][d], dp[i+dx[k]][j+dy[k]][d-1]+ dist[i][j][k]). 즉, 직전 위치 (i+dx[k], j+dy[k])에서 상하좌우로 이동해 온 거리 dist[i][j][k]를 더한 값과 현재 값 중 최솟값을 계속 관리해준다.
논리적으로 이렇게 하면 맞아야 정상이겠지만... 예제 중에 볼록다각형이 아닌 테케가 하나 있다. 게시판에 글을 쓰긴 했으나 아직 반영되진 않았다. 직접 출처인 SEERC 2005에서 데이터를 받아서 확인해보니, 미세하게 안쪽으로 파고든 점이 하나 있는 다각형이 있었다. 이를 예외처리하기 위해, 선분의 중점을 잡고 그 중점이 모든 다각형의 안쪽에 있는지도 판정했다. 수정 요청이 반영되었으며, 재채점까지 완료되었다.
