2018 PPC 풀이

https://leo630.tistory.com/92 이 글에서 이전 년도 PPC 문제들 풀이를 작성하기로 했었는데, 올해 대회가 3일 후이기 때문에 우선은 2018년도 대회 풀이를 써보려 한다. 2019년 대회는 쓰지 않을 예정인데, 아직 다 풀지도 않았고 + 뭔가..뭔가인 문제들이 좀 있고 + 무엇보다 에디토리얼이 있길래 생략하도록 하겠다. 우리 학교 대회인 만큼 평소 쓰던 풀이들보다는 정성들여 써보도록 하겠다.

 

A. Caesar Cipher

문제 소재로 자주 등장하는 카이사르 암호인데, 다른 문제들에 비해 까다로운 부분이 몇 군데 있다.

1. $k$의 크기가 크다. 이는 어떤 알파벳을 26번 밀면 다시 돌아온다는 것을 이용해, $k$를 26으로 나눈 나머지를 취한 후 진행해도 똑같은 결과를 얻을 수 있다.

2. 공백 포함 입력을 받아야 한다. 이는 아마 gets() 또는 getline(cin, s)와 같은 방법을 사용하면 될 것이다.

3. 대/소문자가 모두 들어올 수 있다. if문으로 잘 판별해주자.

위와 같은 사항을 모두 고려해주면 정답을 받을 수 있다.

 

B. Pineapple Farming

웅덩이가 되는 부분을 "물", 웅덩이보다 높은 부분들을 "육지"라 하자.

물과 육지가 되는 경계 높이는 항상 주어진 $HW$개의 높이만 확인해도 됨이 자명하다.

따라서 $HW$번 BFS를 돌려 최대가 되는 컴포넌트의 크기를 찾으면.. TLE를 받는다. $H,W\le 1000$이기 때문이다.

생각을 해 보면, 어떤 경계에서 BFS를 돌린 후 다음 경계로 넘어갈 때 BFS를 새로 돌리는 것은 비효율적이다.

해당하는 높이의 칸만 근처 컴포넌트에 연결해주면 되기 때문이다. 이는 Union-Find를 이용해 처리할 수 있다.

따라서, 낮은 높이의 칸부터 보며 Union-Find를 이용해 연결해주되, 바깥과 연결되어 있지 않은 컴포넌트의 크기 중 최댓값을 계속 구해주면 된다. 같은 높이인 칸이 있을 경우 구현할 때 주의해줘야 할 부분이 있으니 이에 유의하며 구현해주자.

 

C. Binary Counting 

무난한 구현 문제이다. 제한이 작아 대충 구현해도 정답을 쉽게 맞을 수 있다.

문제에 해야 하는 것이 다 적혀 있고, 쉬운 문제이므로 자세한 풀이법은 생략하도록 하겠다.

 

D. Apples and Bananas

갑자기 영어가 등장해 사람을 당황시키는 문제이다. 요약하자면, Alice와 Bob이 게임을 하는데 각 플레이어는

1) 사과 하나 제거 2) 바나나 하나 제거 3) 사과 하나, 바나나 세 개 제거 4) 사과 세 개, 바나나 하나 제거

중 하나의 행동을 번갈아가며 할 수 있다. 마지막 과일을 제거하는 사람이 승리한다.

처음 상태에서의 사과와 바나나의 개수가 주어질 때, 승자를 출력하는 문제이다.

비슷한 형태의 게임 DP에 익숙한 사람이라면 문제를 쉽게 해결할 수 있다.

$DP[a][b]$를 사과가 $a$개, 바나나가 $b$개 있는 상황에서의 선공의 승리 여부라 하자.

$DP[a][b]$는 $DP[a-1][b],DP[a][b-1],DP[a-1][b-3],DP[a-3][b-1]$ 중 0이 하나라도 있으면 1, 모두 1이라면 0이다. 초기 상태는 $DP[0][0]=0$으로 정의해주면 된다.

 

E. Pineapple Pizza

기하 문제이다. 이 역시 기하에 익숙한 사람이라면 쉽고, 그렇지 않으면 어려울 것이다.

우선, 점 Q를 원점으로 생각해 360도 각도 정렬을 한 후, 같은 동경을 가지는 점들을 묶어주자.

이후 각 각도를 시작점으로 한다고 가정한 후, 그리디하게 $\frac{n}{k}$개씩 잘라주는 것이 가능한지 판별하면 된다.

시간 복잡도는 $O(N^2)$이다.

 

F. Edge Coloring

간단해 보이지만, 많이 어려운 문제이다. 다행인 것은, 제한이 작아 일단 풀이를 찾는 데에 집중해도 된다는 점이다. 문제에서 요구하는 사항을 자세히 살펴보자.

첫째로, 그래프의 각 component는 독립적으로 생각할 수 있다. 따라서 연결 그래프라 가정하고 문제를 해결하자.

또한, edge를 하나 색칠할 때마다 문제에서 요구하는 값의 총량이 2씩 증가하므로 문제에서 요구하는 값의 총량은 항상 짝수여야 한다. 이 때, $N$이 홀수라면 홀수를 홀수 번 더한 것이 짝수가 될 수는 없으므로 문제의 조건대로 칠하는 것이 불가능하다.

우선, $N$이 짝수인 트리에서 문제의 조건을 만족하는 색칠이 가능함을 보이자.

여러 방법이 가능하지만, 가장 간단한 방법은 모든 정점 쌍에 대해 경로를 지나는 모든 간선의 색칠 여부를 반전시키는 연산을 시행하는 것이다.

한 경로에 대해 이를 시행할 경우 시작과 끝 정점에 대한 홀짝성만 바뀌는데, $N$이 짝수이므로 각 정점에 대한 홀짝성이 $N-1$번, 즉 홀수번 바뀌므로 문제의 조건을 만족하게 된다.

이제 트리에서 간선이 하나씩 추가되는 상황을 보자.

조건을 만족하는 트리에 간선이 하나 추가된다면, 추가된 간선을 색칠하지 않거나, 추가된 간선을 색칠한 후 기존 경로를 반전시키는 두 가지 경우가 가능하다. 

즉, 원래 그래프에서 사이클을 골라 반전시키는 것은 여전히 조건을 만족한다. 따라서, 이 문제는 그래프에서 사이클을 적절히 선택하는 경우의 수를 묻는 문제가 된다. 사이클의 개수는 $2^{cyclebasis}$이며, cycle basis의 개수는 $E-V+1$ 개이다. 각 컴포넌트에 대해 이 값을 구한 후 모두 곱해주면 된다. 

 

G. Turf Wars

각 영역을 포기했는지에 대한 여부를 $A_{ij}$라 하자.

한 $i$에 대해 포기된 영역은 최대 1개여야 하니 $\mathrm{\neg }{A}_{ij}\vee \mathrm{\neg }{A}_{ik}$를 만족해야 하고,

겹치는 두 영역에 대해 최소 하나는 포기되어야 하니 $A_{ij}\vee A_{kl}$을 만족해야 한다.

이를 모두 추가한 후 2-SAT을 돌리면 문제를 해결할 수 있다.

 

H. Pen Pineapple Apple Pen

그냥 구현 문제이다. 연속된 경우만 세면 되므로 편하게 짜면 된다.

pPAp가 하나 발견되면 마지막 p 이후로 건너뛰는 것을 반복해주자.

 

I. Line of Bentham

각 사람이 뒤 3사람에게만 영향을 받는다는 점을 주목하자.

$DP[i][bit]$를 가장 $i$번째 사람까지, 최근 3명이 요원으로 바뀌었는지 나타낸 것을 bit라 하면 수식을 열심히 정리해 점화식을 세워줄 수 있다. 초기항과 점화식 정리하는 과정이 살짝 귀찮긴 하다.

 

J. First In Last Out

보기 쉽지 않은 Output Only 문제이다. 뭘 해야 하는지는 문제에 잘 나와 있고, 10진수였어도 귀찮았을게 16진수라 더 귀찮다.

위 숫자들만 정해주면 STACK에 해당하는 숫자들은 자동으로 정해지니 이를 잘 구현해보자.