Merry Problem Solving 1일차

Merry Problem Solving을 하고 있습니다! 2018/12/21부터 2019/1/1 까지 매일 앳코더(https://atcoder.com)의 정해진 점수만큼의 문제를 푸는 스터디입니다! 백준 온라인 저지 슬랙(https://acmicpc.net, https://acmicpc.slack.com) 의 #2018_merry_ps 채널에서 진행하고 있습니다. 저는 하루에 총 1400점을 풀기로 했습니다.

사실 앳코더는 점수에 따라 문제의 난이도차가 꽤 나기 때문에 ARC의 F번을 2개 풀어서 1400점을 채우는게 보통이나... 오늘 너무 바빴기 때문에 ARC의 D 3문제를 풀었습니다.

문제의 한국어로 간단하게 정리한 것과 풀이를 적습니다.

---

091D - Remainder Remainder

문제: 두 정수의 쌍 (a, b) 중에서, 1 ≤ a, b ≤ N 이면서, a를 b로 나눈 나머지가 K 이상인 것의 갯수를 세시오.

풀이: mod를 규칙적으로 보기 위해서는 b가 고정되어있으면 편하기 때문에, b를 고정시켜 놓습니다. b를 고정시킨 경우에는 어떤 수를 b로 나눈 나머지는 0, 1, 2, 3, ..., b-1 까지 갔다가, 다시 0부터 시작해서 1씩 증가하고, b-1 다음엔 0으로 돌아온다는 사실을 알 수 있습니다. 그래서 이렇게 돌아가는 수열 중에서 K 이상인 것의 갯수를 세는 것은, 반복되는 부분인 0, 1, 2, 3, ..., b-1이 몇번 반복 되는가와, 가장 마지막에 어떤식으로 수열이 끝나는지를 알면 알 수 있습니다. 자세한 수식은 코드의 수식을 보면 알 수 있습니다.

코드: https://atcoder.jp/contests/arc091/submissions/3832755

---

092D - Two Sequences

문제: 길이 N의 두 수열 a와 b가 주어진다. 모든 가능한 i와 j에 대해서 a_i+b_j의 합 N²개를 모두 XOR 한 값을 구하시오.

풀이: 모든 합을 구해서 XOR하는것은 구하기 때문에, XOR을 구할때 비트별로 볼 것 입니다. 우리가 어떤 특정한 2^B 에 해당하는 비트를 볼 때, 그 위에 있는 비트는 영향을 주지 않습니다. 중요한 것은 우리가 구하려는 비트(2^B)에 있는 값과, 그보다 하위 비트(작은 두 수를 더해서 2^B의 비트에 영향을 줄 수 있음)에 있는 값 입니다. 한 비트에 대해서 XOR은 1이 홀수개 있는지 짝수개 있는지 묻는 연산이기 때문에, 우리는 결국에는 해당하는 비트의 1의 홀짝성을 알려주면 됩니다. 즉, 이 비트에 영향을 홀수번 주었나, 짝수번 주었나를 묻는 문제입니다.

  일단 우리가 구하려는 비트 부터 살펴봅시다. 한 원소의 구하려는 비트가 1이라는 것은, 합 N개의 비트에 영향을 주었다는 의미입니다. 그래서 우리는 수열에 해당하는 비트의 원소가 몇개 있는지를 살펴보면 됩니다. 이제 우리가 구하려는 비트에 영향을 끼치는 갯수는 구했습니다.

  이 후에는, 우리가 구하려는 비트보다 하위 비트에 영향을 주는 갯수만 세면 됩니다.

그래서 우리는 이 문제를 비트마다 구하는 문제로 바꾸면, 각 수열의 원소는 2^B 보다 작고, 2^B에 해당하는 비트가 0인지 1인지를 구하는 문제가 됩니다. 2^B에 해당하는 비트가 0인지 1인지 구하는 문제이지만, 어떤 수열의 두 원소의 합은 2^B의 두배를 넘지 못하기 때문에, 결국 합해서 2^B보다 큰 합의 갯수를 세는 문제로 바뀝니다. 이 문제는 sliding window를 사용하거나, 아니면 binary search를 사용해서 간단하게 구할 수 있습니다. 어떤 한 원소가 x이면, N-x보다 크거나 같은 수의 갯수를 std::lower_bound 등을 이용해 간단하게 세어 줄 수 있습니다. 제 구현은 후자를 사용했고 코드는 다음과 같습니다.

코드: https://atcoder.jp/contests/arc092/submissions/3832874

---

093D - Grid Components

문제: A와 B가 주어졌을 때, 흰색 connected component의 갯수가 A개, 검정색 connected component의 갯수가 B개인 격자를 아무거나 찾아서 출력하시오.

풀이: 이것은 저의 풀이고, 다양한 풀이가 존재할 수 있습니다.

  A가 1인 경우를 풀려고 해 봅시다. 일단 B가 0이면, 흰색으로 전체를 덮으면 됩니다. 여기서 B가 매우 크다고 해 봅시다. 그러면 흰색 component에 검정색 component 여러개를 끼워넣는 방법이 되어야 합니다. 그래서 우리는 흰색 component에 검정색 component를 서로 영향을 주지 않게 흰색끼리 연결되어있는 상태로 추가할 수 있습니다. 마치 수박에 있는 수박씨 처럼 흰색에다가 검정색으로 점을 서로 띄어서 찍어주면 됩니다. 이럴 경우에는 A가 1인 경우를 풀 수 있습니다. B를 추가하는게 점을 찍는것 입니다.

  마찬가지로, 하얀색을 한 칸 추가할 수 있는 환경을 만드려면, 검정색으로 전체를 덮으면 됩니다.

  저는 하얀색과 검정색을 반 반 나눠서 칠한 후 (A = B = 1),  검정색과 하얀색으로 점을 B-1, A-1개 각각 찍는데 서로 최소 2씩 거리가 나게 찍었습니다. 이렇게 찍은 경우에는 하얀색도 검정색도 배경은 연결되어 있다는 것을 알 수 있습니다.

  이 문제는 다양한 풀이가 존재하고, 우리가 만들어야하는 격자의 크기가 작을 경우에 만들 수 있는가? 를 물어보는 문제도 재밌을 것 같습니다.

코드: https://atcoder.jp/contests/arc093/submissions/3832898