4월 29일 연습 (JOI 2016)

다섯시간동안 시간을 재고 문제를 풀었다. JOI Final Round 2016셋을 돌았다. 오후 3시 30분에 시작해서 오후 8시 30분에 끝났다.

 

풀이는 다른 글에 정리할 예정이다.

 

결과

 

100 / 100 / 100 / 100 / 34, 총점 434점

 

연습 기록

0:00 ~ 0:05

JOI 본선은 난이도 순서이기 때문에, 3번부터 풀기로 했다. 3, 4, 5번 문제를 읽었다.

 

0:06 ~ 0:07

3번 풀이 찾았다. bfs를 돌아서 최단 경로 dag를 구하고, 1과 i가 dag 간선으로만 이루어져 있다면 1-i 최단경로가 보존된다. 이 사실을 이용하면 풀 수 있다.

 

0:08 ~ 0:25

구현했다. 화장실을 갔다오기도 했고, 여러 구현 실수가 좀 많아서 늦어졌다. 제출하니까 틀렸고, 약간의 디테일이 틀렸음을 알게 되었다. 최단경로가 작은 도시부터 불만이 생기는 시점을 확정해야 하는데, 유파를 쓰는 이상한 풀이를 냈었다.

 

0:26 ~ 0:35

다시 고쳤고, 한 번에 맞았다.

0:36 ~ 0:48

4번 문제에 대해서 고민해 보았다. 부분 문제 1, 2까지는 나이브 알고리즘으로 풀렸고, 부분 문제 3에 대해서 고민해 보았다. 더블카운팅과 비슷하게, $i$일의 시작점을 원점으로 할 때 $(a, b)$에 있는 각 사각형에 대해 $(a, b)$ 사각형이 $i$일에 최초로 그려지는 $i$의 조건을 $O(N^4)$ 정도에 구할 수 있다는 사실을 관찰했다. 뭔가 좀만 고치면 만점 풀이가 될 것 같아서 당장 구현하지는 않기로 했다.

0:49 ~ 0:57

4번의 정해를 찾았다. 결과적으로 $i$일에 최초로 그려지는 정사각형의 갯수는 $4N$개 이하이므로, 그냥 이 사각형들에 대해서만 보면 된다. 바로 구현하기로 했다.

0:58 ~ 3:22

구현에서 심하게 말렸다. 로직도 복잡하고, 코드도 길고, 처리해야 할 예외 케이스도 진짜 많다. 아래는 내가 한 예외 처리들이다.

 

1. $K$일중 첫날 아침, 조이는 $(0, 0)$에 표시를 한다. 다른 날들은 $N$개씩 점이 찍히는데, 이것 때문에 첫 날이나 $(0, 0)$을 예외처리해야 한다. 나는 $(0, 0)$이 없다고 생각하고 답을 구한 다음에, $(0, 0)$이 둘째날 이후에서 다시 방문되는 경우가 없다면 $(0, 0)$을 포함하는 네 개의 정사각형에 대해 사각형이 형성되었는지 일일히 확인하는 방법을 썼다.

 

2. $K=1$인 경우 (뭔가 예외처리 안 하고도 될 것 같은데, 잘 모르겠다)

 

3. 하루동안 총 이동한 거리가 수직 또는 수평인 경우 : 각 점을 전날에 방문하는지 체크하는 과정에서 예외 처리가 필요하다.

 

다 코딩하고 제출했더니 15점이 떴다.

 

3:23 ~ 3:41

디버깅은 생각보다 쉬웠다. 두 개의 반례를 찾고, 다 고치니까 맞았다.

7 100
EEESWWW

13 2
SSSEENWNENWWN

 

3:42 ~ 3:51

2번을 풀었다. prefix에 있는 j, jo의 수, suffix에 있는 o, oi의 수를 저장하면 선형에 풀린다.

 

3:52 ~ 4:00

1번을 풀었다. $O(NM)$ 나이브 dp를 코딩하면 된다. 뭔가 그럴듯한 최적화가 있을 것 같이 생겼는데, 잘 모르겠다.

 

4:01 ~ 4:26

5번 문제의 부분문제 2번의 풀이를 찾았다. 기본적인 아이디어는 전체 과정을 거꾸로 생각하는 것이다. 즉, 최종 상태의 각 $(i-1, i)$ 부분에 해당하는 지표가 처음 상태에서는 몇 미터였는지를 구하는 것이 문제이고, 각 영역이 연산 실행 이전에는 어디에 있었는지를 $O(1)$에 구할 수 있다. 따라서 $O(NQ)$에 풀 수 있다. 전체 화면을 45도 반시계 방향으로 회전해서 시뮬레이션하면 구현을 쉽게 할 수 있다.

 

뭔가 세그먼트 트리 등을 사용해 조금만 더 발전시키면 정해가 될 것 같고, 어차피 한 문제의 섭테 하나밖에 안 남았는데다 구현까지 쉬워 보여서, 끝나기 직전까지 생각이 안 나면 코딩하기로 했다.

4:27 ~ 4:50

세그먼트 트리 쪽으로 초점을 맞추어서 생각을 해 보았는데, 별로 진전이 없었다. 끝나기 20분 전쯤 코딩해서 맞았다. 34점 받았다.