HI-ARC PS톤 후기

학회에서 주말 동안 문제 풀면 상 받는 대회를 연다고 해서 호다닥 참가했다. 결과는 예상대로 1등.

구체적인 공지나 홍보가 없어서 그런지 다들 별로 참여 안해서 노잼이 돼버렸다.

이하는 간단한 풀이이다.

 

A. 희원이의 뉴욕 생활

https://www.acmicpc.net/problem/2524

쓸데없이 지문이 길다. 맨하탄 거리와 유클리드 거리를 알면 간단한 문제.

그림에서 검은 점은 점 A와 B를 나타낸다.

A와 B 사이 점선이 맨하탄 거리로 최단 거리임이 자명하다. 이때, 대각선이 적절히 있다면 빨간 점선 대신 빨간 실선을 타고 이동할 수 있다. 따라서 (전체 점선 길이) - (빨간 점선 길이) +(빨간 실선 길이) 가 답이다.
대각선을 활용할 수 없는 경우는 (1) A와 B로 이루어진 직사각형(초록)을 지나지 않는 경우와 (2) 대각선의 기울기와 진행 방향이 엇갈리는 경우이다.

1번은 대각선을 나타내는 방정식에 x, y를 적절히 대입해서 확인해보면 되고, 2번은 A―B의 위치 관계와 기울기를 비교해보면 된다.

허용 오차가 1e-9라 무서워서 long double 썼는데 끝나고 다시 내보니 double 써도 맞았다.

 

B. 킥

https://www.acmicpc.net/problem/11566

m이 작다. gap, offset에 대하여 이중 반복문으로 완전 탐색을 돌려버리면 된다.

 

C. 성냥

https://www.acmicpc.net/problem/2029

주어진 격자를 잘 파싱한 뒤, 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으로 받고 콤마와 나눗셈기호를 토큰으로 파싱하자.

 

E. 무제

https://www.acmicpc.net/problem/9548
문제 설명부터가 단순하다. 생각할 것도 없는 그냥 string 사용법 연습 문제

 

F. 망가진 키보드

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이므로 시간 내에 해결할 수 있다.

 

H. 최종 순위

https://www.acmicpc.net/problem/7775
d가 1일 때와 아닐 때로 나눠서 생각해볼 수 있다.

먼저 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이다.

 

K. 정사각형

https://www.acmicpc.net/problem/3614

	문제의 직사각형을 좌표평면으로 옮겨서 생각해보자. 가로길이 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)

아무리 생각해도 골드4의 난이도는 아닌 것 같다.

 

N. 도미노

https://www.acmicpc.net/problem/1073

도미노에 적힌 수를 정점, 도미노를 간선으로 하는 그래프로 모델링을 해 보면 이 문제는 그래프에서 서로 다른 오일러 회로의 개수를 세는 문제로 해석된다. 직접 다 세볼 수는 있겠지만, 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)는 미리 전처리로 구해 둘 수 있는데, 잘 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

d = 2,   f(d) = ( 2C2 ) / ( 1 )

d = 4,   f(d) = ( 2C2 * 4C2 ) / ( 1 * 2 )

d = 6,   f(d) = ( 2C2 * 4C2 * 6C2 ) / ( 1 * 2 * 3 )

d = 8,   f(d) = ( 2C2 * 4C2 * 6C2 * 8C2 ) / ( 1 * 2 * 3 * 4 )

이렇게 이전 항을 활용해 f(d) = f(d-2) * ( dC2 / (d/2) )로 구할 수 있다.

 

O. 팰린드롬 보행

https://www.acmicpc.net/problem/12950

팰린드롬 문자열의 양 끝에 같은 문자를 추가하면 팰린드롬 문자열이라는 점을 활용하자. 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테이블을 아래 첨부한다. (사실 그려놓고 설명에 끼워 넣을 데를 모르겠어서 여기서 넣었다.)