8월 1주차 Weekly PS

• Recent Updates
• Rounds
  • Samsung SCPC Round 2
  • Codeforces Educational Round 112
  • Codeforces Round 736 (Div 1)
• Problems
  • CF Edu112 E - Boring Segments
  • CF R736 Div1 B - Integers have friends
  • CF R736 Div1 D1 - Gregor and the Odd Cows (Easy)
  • USACO 2018 February Platinum Problem 3 - Cow Gymnasts (BOJ 15744)

July 29 - August 07, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 올려놓은 코드를 볼 수 있습니다.

읽는 사람이 문제를 읽고 조금 생각해봤다고 가정하고, 대략적인 아이디어만 간단히 적을 생각입니다 ㅎㅎ

Recent Updates

• SCPC Round 2에서 개고생했습니다. ㅋㅋ!

Rounds

Samsung SCPC Round 2

• 포스팅 링크

Codeforces Educational Round 112

• Div2 기준 274등, Rating 1947 -> 1995 (+48)
• Performance 2096
• 몇달만의 Codeforces 복귀전.
• Div2지만 E번까지 풀어서 굉장히 기분이 좋았습니다. 복귀전인것치고는 레이팅도 많이 올랐고…

Codeforces Round 736 (Div 1)

• Div1 기준 466등, Rating 1995 -> 2055 (+60)
• Performance 2200
• UCPC도 못나가고 하다보니 그냥 CP가 하고싶어져서 좀 자주 돌기로 했습니다. 오렌지 파킹하고 ICPC 팀 찾아야죠.
• C번에 비해 D1번이 많이 쉬웠습니다.

Problems

CF Edu112 E - Boring Segments

• 난이도 2100
• 어떤 subset을 골라서 전체를 커버하되, 가중치의 최대-최소 값을 최소화해야 합니다.
• 이러한 문제를 Two pointer라는 방법으로 잘 해결할 수 있습니다. 또는, 각 시작점에 대해 가능한 끝점을 이분 탐색해도 됩니다.
• 다만, 두 경우의 차이는, $a-b$ 를 쓰다가 $a-(b+1)$ 을 쓰는걸로 전환하는게 빠르면 투포인터를 쓰고, 임의의 $a-b$를 시도하는 쿼리가 빠르면 이분탐색도 쓸 수 있습니다.
• 이 문제는, 후자의 쿼리가 어렵기 때문에 (가능할거같긴한데 사실 잘 모르겠습니다) 투포인터를 씁니다. 따라서 고른 $[l_i, r_i]$ 들의 집합이 한개만큼 바뀔때 쿼리당 시간이 짧아야 합니다.
• 하나를 고를 때마다 $[l_i, r_i]$ 에 1을 더하고 (골랐던걸 뺄때는 당연히 -1), 마지막에 $[1, n]$ 의 최소값이 0인지 (커버하지 못함), 0보다 큰지 (커버함) 판정할 수 있습니다. 이 두 연산 모두 Lazy propagation이 적용된 segment tree로 잘 할수 있음을 알고 있습니다. 이경우 구간 하나를 추가하거나 빼는데 걸리는 시간이 $O(\log n)$, 판정 시간도 $O(\log n)$ 입니다.
• 이제, 마지막으로 생각할 것은 원래 문제에서는 $[1, 3], [4, 5]$ 가 겹치는 것으로 인정되지 않지만 세그트리로 바꿀때는 전체를 커버한다는 False positive의 가능성입니다. $[l_i, r_i]$ 들을 세그에 더할때는 $[l_i, r_i)$ 로 바꿔서 더하면 됩니다.
• 여담으로, 저는 $m, n$ 의 범위를 헷갈려서 삽질하다가 1시간 59분 51초에 대회종료 9초를 남겨두고 AC를 받았습니다. ㅋㅋ!

CF R736 Div1 B - Integers have friends

• 간단하게 생각할 수 있는 것은, 주어진 수들의 인접한 수들 간의 차를 새로운 배열로 만들고 나면, 이 배열에서 어떤 sub-array를 뽑아서 그 gcd가 1보다 크면 된다는 것입니다.
• GCD가 1이 아닌 가장 긴 subarray를 찾는 것은 역시 위 문제와 똑같이, 투포인터 또는 각 시작점에서의 이분탐색으로 해결가능합니다.
• 어떤 부분구간의 GCD가 1인지 아닌지 빠르게 판정하기 위해서는, 노드에 gcd값을 저장하는 세그먼트 트리를 사용하면 됩니다.
• 위 문제와 거의 같은 세그 + (투포인터 or 이분탐색) 문제입니다. 저는 위문제는 투포인터를, 이 문제는 이분 탐색을 썼습니다.
• 투포인터 사용시 $O(n \log A)$, 이분탐색은 $O(n \log n \log A)$인데, 이분탐색도 넉넉합니다. GCD는 생각보다 빨라서요.

CF R736 Div1 D1 - Gregor and the Odd Cows (Easy)

• 픽의 정리에 의하면, 볼록다각형의 넓이 $A$, 경계면에 있는 격자점의 수 $B$, 안쪽에 들어있는 격자점의 수 $C$에 대해 $A = B/2 + C - 1$ 이 성립합니다.
• 즉, $A$ 와 $B/2$의 홀짝성이 같다면 $C$가 홀수가 될 것입니다.
• 고를 수 있는 모든 정수점이 짝수좌표를 갖는 상황에서, $A$와 $B/2$의 홀짝성에 대해 생각해 보겠습니다.
• $A$, 즉 넓이는 외적공식을 통해 구할 수 있는데, 어차피 mod 4 위에서 구할 것이므로 원래 점의 좌표의 mod 4 값들만 알아도 충분합니다.
• $B$ 를 mod 4한 값을 알아야 하는데, 잘 생각해 보면 $(x_1, y_1)$ 에서 $(x_2, y_2)$까지 선분을 이을 때 그 위의 정수 격자점의 개수는 $\gcd(x_2 - x_1, y_2 - y_1)$ 이 4의 배수인지 여부에 따라 결정됩니다.
• 따라서, 임의의 세 점 $p_i, p_j, p_k$에 대해, 각 점의 $x, y$ 좌표의 mod 4한 나머지값만 안다면, 이 점들은 사실 $A$와 $B/2$의 부호 면에서는 똑같습니다.
• 점을 네가지로 구분하고 ($x$와 $y$ 좌표를 0 또는 2로), 클래스 0-3의 점들 중 3개를 고르는 경우의 수 64가지를 생각해 줍니다. 같은 클래스의 점을 2개 고를 때 경우의 수는 이항계수로 구해야 함을 기억합시다.
• 코드는 간단하지만 Casework가 좀 있습니다.
• 이문제도 끝나기 10분정도 전에 AC를 받았습니다.

USACO 2018 February Platinum Problem 3 - Cow Gymnasts (BOJ 15744)

• 난이도 Diamond 3.
• 별도 포스팅합니다. 링크