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 \leq 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^{cycle basis}\)이며, cycle basis의 개수는 \(E-V+1\) 개이다. 각 컴포넌트에 대해 이 값을 구한 후 모두 곱해주면 된다. 

 

G. Turf Wars

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

한 \(i\)에 대해 포기된 영역은 최대 1개여야 하니 \(\lnot A_{ij} \lor \lnot A_{ik}\)를 만족해야 하고,

겹치는 두 영역에 대해 최소 하나는 포기되어야 하니 \(A_{ij} \lor 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에 해당하는 숫자들은 자동으로 정해지니 이를 잘 구현해보자.