Codeforces Round #309

이 라운드는 내가 치지는 않았다. 몇가지 이유가 있었는데 1) 시작할때 즈음 코포 서버가 난장판이어서 2) 문제가 mathy하다는 불안감이 계속 들어서 3) 내가 너무 졸려서... 정도.

일단 오늘 일어나서 문제를 봤는데 확실히 2번은 잘못된 가정이었다 ㅠㅠ 그냥 문제가 어렵지 않은 셋이었던듯, 볼걸 하는 후회가 계속 밀려오지만, 그냥 다음 시험을 위한 발판으로 삼자고 자기위안중...

Div2 A. Kyoya and Photobooks

http://codeforces.com/problemset/problem/554/A

사실 그냥 답은 25|S| + 26이다 (....) 하지만 안전이 제일이라 난 Brute force로 짬. STL string + STL set을 쓰면 굉장히 빠르게 코딩할 수 있다.

cpp : http://codeforces.com/contest/554/submission/11753826

Div2 B. Ohana Cleans Up

http://codeforces.com/problemset/problem/554/B

세로줄만 뒤집을 수 있기 때문에, 가로줄의 청소 상태가 다르면, 둘 다 완전히 깨끗해질 수는 없다 는 것을 관찰해야 한다. 가로줄의 내용이 같은 집합끼리는 같이 깨끗해 질 수 있기 때문에, 가로줄 중 값이 같은 애들끼리 묶은 후, 그 중 안에 들어 있는 원소의 수가 제일 많은 것을 찍으면 된다. 말이 참 복잡하나 소스는 참 간단하다. A에서 썼던 소스를 조금만 바꾸면 풀린다.

cpp : http://codeforces.com/contest/554/submission/11753842

Div1 A. Kyoya and Colored Balls

http://codeforces.com/problemset/problem/553/A

어렵게 생각치 말고 그냥 simulation을 하면 된다. 첫번째 공부터 순서대로 집합에 끼워넣는다고 하면, 마지막 공은 맨 뒤로 넣고, 나머지는 알아서 잘 끼워넣는 것이 유일하게 가능한 경우의 수이다. 이러한 경우의 수는 이항계수 C(전체 공 + 넣는 공 - 1, 넣는 공 - 1) 이다. 이항 계수는 2000 * 2000에 미리 계산해 두고 공이 들어올때마다 계산하면 시간 안에 풀 수 있다.

cpp : http://codeforces.com/contest/553/submission/11753610

Div1 B. Kyoya and Permutation

http://codeforces.com/problemset/problem/553/B

문제가 참 복잡하게 써있고 실제로 난 문제 오독으로 인해서 몇번 틀렸었다. 하지만 현실은 걍 쉬운 주제를 이리저리 꼬아놓은 문제.. 문제를 풀면서 다음과 같은 관찰을 순서대로 해나가면, 실제 문제가 그렇게 어렵지 않다는 것을 알 수 있다.

1) Permutation을 그래프로 보고 컴포넌트를 그려보자, 컴포넌트는 실제 순열 상에서 연속해야 한다.

2) 한개의 컴포넌트에 내림차순으로 번호를 매기자, 3개 이상 있으면 내림차순으로 번호를 못 매긴다는 것을 알 수 있다. 즉 컴포넌트의 원소의 수는 1개거나 2개이다.

K번째 수열을 반환하라고 했으니 먼저 dp 식부터 짜는 게 우선일 거다. 위 내용대로라면 dp[i] = dp[i+1] + dp[i+2]이다. 허무하다! K번째 수열을 찍는 것은 그냥 재귀함수로 trace해주면 된다. 모르겠으면 cpp 참조.

난 소스상에서 오버플로우 처리를 신중하게 했는데, 실제로는 f(50)이 long long을 한참 밑도니 long long만 쓰면 걱정할 필요는 별로 없다.

cpp : http://codeforces.com/contest/553/submission/11755731

Div1 C. Love Triangles

세 정점을 봤을 때 정점이 Hate - Hate - Love, Love - Love - Love의 관계여야 하는데, 이는 Hate하는 두 원소는 다른 집합에, Love하는 두 원소는 같은 집합에 있다는 것을 의미한다. 다른 집합과 같은 집합을 얘기했을 때 우리가 바로 떠올릴 수 있는 것은 2-SAT이다. True 집합, False 집합이 있을 때, Hate가 들어온다는 것은 (Ai != Bi) 라는 Clause, Love가 들어온다는 것은 (Ai == Bi) 라는 것을 의미한다. 2-SAT은 SCC를 이용해 선형 시간에 구할 수 있다.

2-SAT을 구하고 모순이 되는 경우를 지웠다면, 이제 서로 묶여있는 정점들을 생각하자. 컴포넌트의 개수가 T라면, 답은 2 ^ (T/2-1) 이다. -1은 문제 조건이고, T/2는 자신에 대한 논리절이 있을 때 자신의 역에 대한 논리절이 있으니 반으로 나눠준 것이다. (실제로 모순이 없으면 T % 2 == 0).

... 하지만 2-SAT은 너무 복잡하다! 다행이도, (A != B) / (A == B)의 논리절만 들어오는 특수한 경우의 2-SAT에는 Union-Find를 통한 깔끔한 풀이가 있다. 저러한 2-SAT은 Union-Find로 구현할 수 있는데, A != B 일 경우 (A,~B) 와 (~A,B) 를 Union, A == B일때 (A,B)와 (~A,~B)를 Union한 후 그냥 컴포넌트 개수는 하던 대로 구해주면 된다. 아, A와 ~A가 같은 집합 안에 있으면 모순이다. 끝!

이 특수한 경우의 2-SAT은 종만북에도 있는 유명한 예제로써 (https://algospot.com/judge/problem/read/EDITORWARS) 보통 사람들이 이걸 처음 배울 때 이게 2-SAT인줄 모르고 배우는 듯 한데, 아무리 생각해도 저게 2-SAT임을 알고 있어야지 저걸 제대로 짤 수 있다고 생각한다. 아무튼 저 문제는 정말 여기저기 많이 나오는 문제니 꼭 익혀두자.

cpp : http://codeforces.com/contest/553/submission/11753964

Div1 D. Nudist Beach

http://codeforces.com/problemset/problem/553/D

문제를 딱 보면 parametric search의 냄새가 스멀스멀 풍겨온다. 조금 더 정확히 이유를 얘기하자면 "Strength가 주어지는 형태가 분수의 형태이며" "최솟값을 최대화하는 문제이기 때문에" .. 둘다 보통 parametric search로 잘 풀리는 유형들이다. (특히 전자는 거의 100%인듯)

그러니 T를 답이라고 한 후 "최솟값을 T로 했을 때 그러한 집합을 찾을 수 있는가?" 로 문제를 조금 변형시키자. (저 문제를 풀 수 있으면, 답을 구할 때는 이진 탐색만 하면 된다) 나는 여기서 너비 우선 탐색을 사용하였다. 먼저 K = 0일 때 답이 1임은 너무 자명하다. 즉 답에 걸림돌이 되는 것은 집합 K 뿐. 먼저 K를 모두 큐에 넣어준 후, K와 연결된 모든 점의 degree를 지워주자. 만약에 degree를 지웠을 때 해당 점의 strength가 T 미만이 된다면 이를 큐에 넣어준 후 반복한다. 이 알고리즘은 모든 정점을 돌면서, 그 정점의 정당성을 계속 체크해나가기 때문에 정당하며, 너비 우선 탐색을 통해 구현했을 때 선형 시간에 작동한다.

큐에 모든 정점이 한번 정도 들어갔었다면 최솟값이 T일때 그러한 집합은 없다. 들어가지 않은 정점이 하나라도 있다면 그러한 집합은 있다. 답을 찍어줄 때는 들어가지 않은 정점을 찍자.

실수를 동반하니 eps를 써주지 않으면 WA를 볼 수 있다. 조심하자.

cpp : http://codeforces.com/contest/553/submission/11756454

E는 짱 어렵다는 듯 하니 생략한다.