5등까지 상품이 나가는데, 시작하고서 가벼운 마음으로 대충 문제 훑어보다가 5~10분 정도 날렸다. 만약에 바로 A번 잡고 풀었다면 3솔도 할 수 있었는데 아쉬웠다.
A. permutation making (00:14)
최대한 누적합이 같게 만들어줘야 한다. 누적합을 N으로 나머지 연산을 하므로, N의 배수들은 모두 똑같이 0으로 취급된다. 따라서 누적합이 N의 배수가 나오도록 N, 1, N-1, 2, N-2, ... 이렇게 배치해주면 된다. 그러면 홀수 번째 원소들은 모두 같고, 짝수 번째 원소들은 다 다르므로 조건을 만족한다.
D. 신촌 수열과 쿼리 (01:16)
2번 쿼리를 살펴보면, 구간 [l, i]에서 모든 원소가 j 이상이 되도록 l을 최대한 감소시키고, 구간 [i, r]에서 모든 원소가 j 이상이 되도록 r을 최대한 증가시키면 된다. 최솟값 세그트리를 사용해서 구간 [l, i] 또는 구간 [i, r]에 j보다 작은 원소가 있는지 O(logN) 안에 찾을 수 있다. 이분 탐색을 한 번씩 사용해서 조건을 만족하는 동안 l의 최솟값 그리고 r의 최댓값을 각각 구할 수 있다. 이렇게 하여 O(log log N) 안에 2번 쿼리를 해결할 수 있다.
1번 쿼리는 그냥 세그트리에 update해주면 된다.
문제를 잘못 읽어서 굉장히 헤멨다. 2번 쿼리의 구간에 i가 포함되어야 한다는 조건을 놓쳐서 머지소트트리+금광세그를 짜야 하나 고민했다.
G. 신촌방위본부 (업솔빙)
나무가 불에 타는 조건은, 내분점 공식과 동일하다. 즉, 미사일이 떨어진 좌표를 이어서 만든 도형의 내부(모서리에 걸친 점도 포함)에 있는 모든 나무가 불에 탄다는 뜻이다. 미사일이 떨어진 좌표들의 볼록껍질을 구하고 볼록다각형의 넓이를 구한다. 볼록다각형이 격자점 위에 있으므로 픽의 정리를 이용하면 다각형 내부에 있는 점의 개수를 구할 수 있다. 여기서 볼록다각형의 내부에 있는 보호막의 개수만큼 빼면 답이 된다.
미사일의 수가 2개 이하인 경우는 볼록다각형이 만들어지지 않으므로 예외처리를 해줘야하는데, 다 짜고 이 예외처리 부분을 짜다가 대회가 끝났다. 딱 3분만 더 있었다면 맞을 수 있었는데 매우 아쉽다.
자다 일어났더니 대회가 2시간 가량 밖에 남지 않았다. solved.ac 뱃지 기준인 100점만 넘기자는 마인드로 대충 풀었다.
C. ko_orange (02:45)
[2100, 2400) 구간 내에서 이분 탐색을 하는데, 쿼리의 답이 잘못 주어질 수 있다. 그냥 같은 쿼리를 두 번씩 물어봐서 첫 번째 서브태스크만 해결했다.
A. 오렌지컵 출제하기 (03:02)
문제를 준비 시간으로 정렬하고 작은 것부터 그리디하게 골라 나갔다. 고르면서 어떤 출제자가 L개 이상의 문제를 내야 한다면 그 문제를 뛰어 넘는다. 이렇게 하여 세 번째 서브태스크까지 해결했다.
이 문제를 풀고 총 점수가 88점이었기에 100점만 만들자는 생각으로 모든 문제를 한 번 훑어보면서 찍먹했다.
D. 오렌지 섬 여행하기 (04:14)
첫 번째 서브태스크를 해결하기 위해 직접 $n=7$까지 손으로 그려 보니, 왠지 모든 n에 대하여 오렌지를 다 먹을 수 있을 것 같았다.
만약 $n=i$일 때 오렌지를 전부 먹을 수 있는 경로가 있다고 하면, $n=i+1$일 때 인접한 두 정점 사이에 $i+1$을 잘 끼워 넣으면 된다. $i+1$이 두 정점과 서로소일 때 끼워 넣을 수 있다. 또는 맨 앞이나 맨 뒤에는 인접한 한 정점과 서로소이기만 해도 된다. 이런 조건을 만족하면서 N까지 그리디하게 끼워 넣다 보면 해결할 수 있다.
혹시 몰라서 assert를 넣은 채 제출했는데 한 번에 맞았다.
I. 오렌지 키우기 (04:16)
$K=0$이라면 심는 즉시 오렌지를 수확할 수 있고, 이는 오렌지를 심을 수 있는 지점에 방문하고 돌아오는 데 걸리는 시간과 같다. 따라서 오렌지를 심을 수 있는 지점 중 가장 먼 곳의 거리를 답이다. 이렇게 하면 첫 번째 서브태스크를 해결할 수 있다.
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테이블을 아래 첨부한다. (사실 그려놓고 설명에 끼워 넣을 데를 모르겠어서 여기서 넣었다.)
