AtCoder Regular Contest 074

C - Chocolate Bar

간단한 수식으로 나올 것 같았는데, 예외적인 경우를 생각하기 귀찮아서 삼분검색 돌렸다.

원래의 경우에서 상하좌우 바꾸고, 90도 돌리는 것만 고려해주면 되어서 실제 작성한 코드는 짧다.

소스코드

D - 3N Numbers

왼쪽에서부터 어느 곳까지 N개를 고르고, 그 이후 구간에는 N개를 고르는 것으로 볼 수 있다.

따라서 전처리로 왼쪽에서 어디까지 N개를 골랐을 때의 최댓값, 오른쪽에서 어디까지 N개를 골랐을 때의 최솟값을 구해놓으면 답을 쉽게 계산할 수 있다.

소스코드

E - RGB Sequence

문제를 안 읽어봤다.

F - Lotus Leaves

플로우 네트워크를 만들고, 정점을 이분화 한다.

시작점과 도착의 경우, 이분화한 정점 사이의 용량을 무한대로 준다.

이 외의 정점들은 이분화한 정점 사이의 용량을 1로 준다.

같은 행이나 열에 있는 경우 각 정점의 나가는 정점과 들어오는 정점 사이에 용량을 1로 준다.

시작점 들어오는 정점에서 도착점 나가는 정점으로의 최대 유량을 구하면 그것이 min-cut과 동일하기 때문에 답이 된다.

소스코드