오전 셋

AtCoder CF 17 Qual A를 돌았다. 이게 실제로 두시간셋이라니…

D. Four Coloring
45도 돌리고, 변의 길이가 d인 정사각형에 대해서 이웃한 8방의 칸들이 전부 다른 색이면 된다. 색이 4개니까 각 좌표에 기우성에 맞춰서 칠하면 된다.

E. Modern Painting
최종 상태에서 ‘방해받지 않고 뻗은’ 가장 왼쪽의 열을 잡는다. 그걸로 그리드를 분할할 수 있고, 이걸 사용해서 DP를 하면 된다고 한다. 잘 모르겠다.

F. Squeezing Slimes
슬라임을 합한 형태가 대략 빽빽한 이진 트리 모양이 될 것이라고 예상할 수 있다. 같은 깊이에서 합쳐진 슬라임들을 한꺼번에 처리해준다고 하면, 각 Ai에 대해서 양쪽으로 붙일 수 있는 높이가 2가지 혹은 1가지로 나온다. 이를 통해 DP를 해주면 된다고 한다.

오후 셋

뭔지 모를 JAG Contest를 풀었다. 듣기에는 우리나라 UCPC같은 대회라고 한다.

D. Revenge of the Broken Door
단순히 두번째 최단경로를 구하는 식으로는 안된다.
게임 문제를 푸는 식으로 생각할 수 있다.
한 점에서 아직 끊긴 간선이 등장하지 않았을 때, S에서 v로 가는 비용을 f(v)라고 하자. 또, v에서 T로 가는 최단경로를 아무거나 하나 잡았을 때, v에서 향해야 할 간선이 끊겼을 때에 대체로 택할 최단 경로의 길이를 g(v)라고 하자.
대략 답은 f(T)=min(f(v)+g(v))가 된다. 이제 f와 g를 잘 구하면 된다.
g(v)는 T에서 뒤집은 간선들을 사용해 다익스트라를 돌리고 그 결과를 트리로 나타내 봤을 때, v의 부모로 가는 간선이 끊긴 것이라고 생각할 수 있다. 그러면 v를 루트로 하는 서브트리 아래에 있는 점들 중에서, 외부로 연결되는 백엣지 혹은 크로스엣지들을 체크하면 된다. 이건 트리 압축을 통해 할 수 있다고 한다(? 모르겠다)
f(v)는 파라메트릭으로 잡고 하면 된다고 하는데, 일단 넘어가자.

I. Revenge of the Endless BFS
피곤하다. 다음에 기회가 되면 자세히 쓰겠다.
행렬곱을 하면서, 파라메트릭을 하면 된다.

J. Farm Village
Ad-hoc류인 듯 하다. 일단 앞에서 받아오고, 뒤의 농장들이 들어올 때 변화량을 계산해서 최적으로 갱신해준다.

K. Conveyor Belt
평행사변형을 가장 컴팩트하게 쌓는 것인데, 그냥 직사각형을 쌓는 것이랑 동일한 논리를 사용할 수 있다. 구간에 값을 더해 줬을 때 그 중 최대값이 답이다.

힘이 빠진다. 좀 더 성실하게 살아야지 싶다.