티스토리 뷰

해법

Google CodeJam 2019 Round 2 풀이

전명우 2019. 5. 21. 17:15

문제 및 채점: 사이트

A. New Elements: Part 1

 

질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자를 질량 순서대로 정렬하려고 한다. 다만, 분자의 질량은 모두 달라야 한다. 이때, 정렬 결과로 가능한 순서는 모두 몇 개인지 구하는 문제다.

 

서로 다른 i와 j에 대해, C[i] ≤ C[j], J[i] ≤ J[j]를 만족하면 질량 X, Y와 상관없이 질량의 대소 관계가 명확하다. 다만, C[i] < C[j], J[i] > J[j]와 같이 원소 C 개수의 대소 관계와 원소 J 개수의 대소 관계가 뒤집혀있을 때에는 질량 X, Y의 비율에 따라 대소 관계가 달라진다. 그리고 질량 X와 Y의 값이 정해지면 순서는 유일하게 결정된다. 이 문제의 풀이는 서로 다른 분자에 대해 같은 질량이 되는 질량 X, Y의 비율을 모두 구하여 가지 수를 구하고 1을 더하면 문제에서 요구한 가능한 순서의 개수가 된다.

 

 

B. Pottery Lottery

 

1번부터 100번까지 차례대로 번호가 매겨진 사람 100명이 게임에 참가한다. 화분이 20개가 있는데, 1번 사람부터 차례대로 나와 자신의 번호표를 임의로 한 화분을 정해 그 화분 아래에 둔다. 100명의 사람이 모두 자신의 번호표를 두고 난 뒤 게임이 종료되며, 가장 적은 수의 번호표가 있는 화분에 번호표를 둔 사람이 게임의 승자가 된다. 만약, 가장 적은 수의 번호표가 있는 화분이 여러 개라면 게임은 무효가 되며 아무도 승자가 되지 않는다.

 

문제는 이 게임에서 100번 사람이 되어 두 종류의 반칙을 적절히 사용하여 자신의 승률을 90% 이상으로 만드는 것이다. 두 종류의 반칙은 다음과 같다.

1. 어떤 사람이 화분에 번호표를 두고 난 뒤, 아주 정교하게 위조된 번호표를 만들어 원하는 화분 아래에 둔다. 위조한 번호표에 번호는 마음대로 적을 수 있다.

2. 어떤 사람이 화분에 번호표를 두고 난 뒤, 원하는 화분을 선택하여 그 화분에 있는 번호표 구성을 확인할 수 있다. 다만, 직전에 번호표를 둔 화분이 무엇인지는 알지 못한다.

 

모든 화분에 100이 적힌 번호표를 위조하여 정확히 하나씩 넣어두자. 그러면, 가장 적은 수의 번호표가 있는 화분이 여러 개가 아닌 경우에는 항상 승자가 될 수 있다. 100번의 차례 중에 20번은 각 화분에 100이 적힌 번호표를 넣어두는데 활용하고, 나머지 80번은 최소 동률을 최대한 없애는데 활용하면 된다. 이때, 가능한 전략은 여러 가지가 가능하다.

 

아래에 첨부된 코드에서 구현한 방법은 80번 중 첫 50번은 1 이상 10 이하 화분 중에 임의로 한 화분을 선택하여 아무 번호표를 아래에 넣어둔다. 즉, 1 이상 10 이하의 화분은 최소 개수의 번호표가 없도록 밑 작업을 한다. 이후 20번은 각 화분에 있는 번호표 개수를 조사하여, 다음 10번 동안 조사한 번호표 개수를 토대로 번호 충돌이 일어나지 않게 동률을 없애는데 집중한다. 이렇게 구현했을 때, 총 250개의 게임 중 평균 약 235 게임의 승자가 된다.

 

 

C. New Elements: Part 2

 

질량이 X인 원소 C가 있고, 질량이 Y인 원소 J가 있다. 분자 N개가 있는데, i번째 분자에 포함된 원소 C의 개수는 C[i]개고, 포함된 원소 J의 개수는 J[i]개다. 원소 C와 원소 J 이외에 다른 원소는 포함되어 있지 않다. 분자들은 질량 순서대로 주어지며, 서로 다른 두 분자는 같은 질량을 가지지 않는다. 이때, 가능한 질량 X, Y를 구하는데, 가능한 X 중 가장 작은 값을 구하며, 만약, 질량 X가 가장 작은 경우가 여러 가지라면 질량 Y도 가장 작은 값으로 구하는 문제다.

 

i < j인 i, j에 대해 C[i] < C[j]이고, J[i] > J[j]인 경우를 생각하면 질량 X와 Y의 비율 Y/X는 다음 조건을 만족해야 한다.

$\cfrac{Y}{X} < \cfrac{C_j-C_i}{J_i-J_j}$

비슷한 경우로, C[i] > C[j]이고, J[i] < J[j]인 경우를 생각하면 다음 조건을 만족해야 한다.

$\cfrac{Y}{X} > \cfrac{C_i-C_j}{J_j-J_i}$

 

이처럼 질량 비율 Y/X에 대해 하한과 상한이 정해진다. 즉, 유리수 $l$과 $r$에 대해, $l < \frac{Y}{X} < r$을 만족하는 가장 작은 $(X, Y)$를 구하는 문제가 된다. 이는 Stern-Brocot 트리에서 이분 탐색을 통해 $O(\lg{X+Y})$ 시간에 해결할 수 있다.

 

 

D. Contransmutation

 

금속 종류 M개가 있다. 금속은 1번부터 M번까지 번호가 매겨져 있다. 연금술을 통하여 i번 금속 1g을 이용하여 R1[i]번 금속 1g과, R2[i]번 금속 1g을 만들 수 있다. 초기에 i번 금속은 G[i]g 만큼 있다. 적절한 연금술 연산을 통하여 1번 금속의 양을 최대로 많이 만드는 문제다. 만약 만들 수 있는 1번 금속의 양이 무한하다면 "UNBOUNDED"를 출력한다.

 

문제 상황을 방향성 그래프로 표현할 수 있다. i번 정점에는 정확히 2개의 나가는 방향 간선이 있는데, 각각 R1[i], R2[i]번 정점을 가리킨다. i번 정점에서 시작하여, 하나 이상의 간선을 통해 다시 i번 정점으로 돌아올 수 있으면 i번 정점을 이용하여 한 종류 이상의 금속을 무한히 만들 수 있다. 이를 통하여 무한히 만들 수 있는 금속(정점)들을 모두 색칠할 수 있다. 이 방법은 그래프에서 SCC(Strongly Connected Component, 강연결요소)를 모두 구하면 편하게 구현할 수 있다. i번 정점에서 하나 이상의 간선을 통해 다시 i번 정점으로 돌아올 수 있는 것의 필요충분조건은 i번 정점이 속한 SCC의 크기가 2이상이거나 i번 정점이 자기 자신을 가리키는 self-edge가 있다는 것이다. 이렇게 일부 무한히 만들 수 있는 정점을 색칠한 뒤에 Flood-Fill을 통해 나머지 무한히 만들 수 있는 정점들도 구할 수 있다. 그러면 이제 정답의 UNBOUNDED 여부를 알 수 있다.

 

정답이 UNBOUNDED가 아닌 경우, 풀이의 핵심 아이디어는 그래프에서 구한 SCC 안에서 무한히 생성 가능한 정점이 없기 때문에 어떤 연금술 연산을 진행해도 SCC 안에서 금속의 총질량은 유지된다는 것이다. 이 아이디어를 통해 SCC의 질량이라는 것을 정의할 수 있고, SCC를 하나의 정점으로 두어 만들어진 DAG(Directed Acyclic Graph, 유향 비순환 그래프)에서 위상 정렬을 통해 1번 정점이 속한 SCC가 가질 수 있는 최종 질량을 구하여 문제에서 요구한 답을 구할 수 있다.

 

댓글
댓글쓰기 폼