Codeforces Round #644 (Div. 3)

Codeforces Round #644 (Div. 3)에 참가했다.

시험이 다음주이기도 하고 잠시 PS를 안하겠다 생각하고 있던 터라 참여할 생각이 없었지만, 밤에 할 게 없어서 15분정도 늦게 register 하고 느긋하게 풀었다.

 

G는 대회 끝나고 업솔브했다.

 

A. Minimal Square

$a<b$ 라고 하면, 정사각형의 한 변의 길이는 $min(2a,b)$ 이면 충분하다.

code

 

B. Honest Coach

정렬한 후, 인접한 값이 최소인 두 개를 기준으로 나눠주면 된다.

code

 

C. Similar Pairs

먼저, $N$이 홀수면 무조건 NO가 답이다.

$N$이 짝수라면, 홀수와 짝수의 개수가 각각 (홀수,홀수) 또는 (짝수,짝수) 인 두 경우가 있다. 후자의 경우는 첫번째 조건 (same parity) 로만 짝지어주면 끝이다. 전자의 경우는 두번째 조건 (두 수의 차가 1) 인 쌍이 하나만 있으면 끝이다. 두번째 조건과 첫번째 조건을 동시에 만족 할 수 없기 때문이다.

code

 

D. Buying Shovels

$N=a \times b$ 라고 하자. ($a \le b$) 이때 $b \le K$ 이면 $b$개짜리 package를 a개 살 수 있다. 따라서 조건을 만족하는 최소 a를 찾으면 되고, 이는 약수를 $sqrt(N)$로 찾으면서 하면 된다.

code

 

E.  Polygon

어떤 지점이 1이면 그 지점의 오른쪽이 벽이거나 1, 또는 왼쪽이 벽이거나 1이어야 한다. 벽을 미리 1로 채워두고 시작하면 구현이 편하다.

code

 

F. Spy-string

주어진 문자열중 하나를 골라서, 모든 위치에 대해 모든 문자를 시도해보면서 조건을 만족하는지 확인하면 된다.

code

G. A/B Matrix

먼저 $N \times A \ne M \times B$이면 무조건 NO이다. 나머지 경우는 잘 하면 되는데, 코드를 참고하자.

code

 

H. Binary Median

Binary String은 이진수로 봐도 무관하다. 즉 대소관계가 똑같이 성립한다. $M \le 60$ 이므로 각 Binary String은 long long 범위의 숫자로 나타낼 수 있다. 따라서 이 문제는 '$[0,2^{M}]$ 범위의 숫자들 중 N개의 숫자를 제외한 상태에서의 중간값' 을 구하는 문제로 바뀐다. 이는 이분탐색으로 해결할 수 있다.

code