7/19 ~ 7/21 PS

 어제는 ucpc, 오늘은 icpc 팀연습을 했다. 힘들다.

 심지어 오늘은 몸살 기운 때문에 컨디션이 너무 안 좋아서 팀연습 때 트롤을 했다..

 

 

 

BOJ 20191 - 줄임말 (G2)

문자열의 i번째 글자의 위치를 이분 탐색으로 찾아주면 된다.

 

BOJ 3654 - L퍼즐 (D5)

어떤 B에 대해, 상하를 true/false로 두고, 좌우를 true/false로 두자. 그리고 B와 연결된 W에 대해, 이 W와 연결된 B에 대해서도 논리식을 세워주면 된다. 나는 2-sat을 연습하기 위해 이렇게 풀었는데, 단순 bfs로도 풀린다고 한다.

 

BOJ 14961 - Untangling Chain (P5)

i번째에, (i-1)번째와 동일한 방향으로 회전하는 경우라면 i칸을 이동하고, 아니라면 1칸을 이동하면 된다.

 

BOJ 14953 - Game Map (G4)

연결된 간선의 개수가 가장 적은 정점부터 확인하여 dp를 돌리면 된다.

 

BOJ 22354 - 돌 가져가기 (P3)

BW가 번갈아 나오도록 각 구간의 최댓값만 남기고 다 지운 상태로 시작하자. \(\ceil{\frac{K-2}{2}}\)개의 돌을 잘 먹어야 한다. 근데, 놀랍게도 양 끝을 제외한 나머지 돌 중 원하는 것을 고를 수 있으므로 그냥 정렬하면 된다.

 

BOJ 21091 - Increasing or Decreasing (P3)

먼저, 구간 \([1, N]\)을 정렬해주자. 그리고, 수열 b의 i번째 원소에 대해, 구간 \([i, idx_{b_i}]\)를 정렬해주면 된다. 우리는 처음에 구간 전체를 정렬했기 때문에, 구간 \([i, idx_{b_i}]\)에서 \(b_i\)가 최솟값과 최댓값 사이에 들어오는 일은 없다. 그리고 N-1개의 원소를 올바른 곳에 배치하면, 나머지 1개의 원소는 알아서 올바른 위치로 들어간다. 정확히 N번의 정렬을 사용한다.

 

BOJ 16525 - Escape, Polygon! (P2)

기준이 되는 선분 \(l\)에서, \(r\)을 ccw가 역전되지 않는 한 최대한 멀리 옮겨준다.

위 그림에서는 초록 선이 \(l\)이고, 빨간 선이 \(r\)이다. 이제 polygon을 가두지 못하는 경우를 셀 것이다. \([l, r]\)에서, 직선 하나를 \(l\)로 고정하고, 나머지 두 직선은 \([l + 1, r]\)에서 고르자. 그리고 이들의 합을 전체 경우의 수인 \({}_{N}C_3\)에서 빼주면 된다. 이 방법은 \([l, r]\)에서 세 직선을 고르는 방법과는 다르게, 경우의 수를 따로 뺄 필요가 없어서 편하다.