[코드포스] Round #839 (Div. 3)

안녕하세요 aim_higher 입니다.

코드포스 Round #839 (Div. 3) 코드리뷰 및 업솔빙입니다.

---

A. A+B?

https://codeforces.com/contest/1772/problem/A

• String(문자열)

 

{a}+{b}의 문자열 형태로 입력이 들어오므로,

아스키 코드값인 a+b에 -'0'씩 두번 해주시면 정답이 나옵니다.

---

B. Matrix Rotation

https://codeforces.com/contest/1772/problem/B

• Implementation(구현)

2x2의 이산적인 정수로 구성된 행렬이 있습니다.

다음 두 조건을 만족해야 "아름답다"라고 표현할 수 있습니다.

 - 각 열에 대해, 첫번째 원소 < 두번째 원소

 - 각 행에 대해, 첫번째 원소 < 두번째 원소

2x2의 행렬의 원소를 시계방향으로 재정렬 시킬 수 있습니다.

2x2이므로 4개의 경우를 판별해보면 되겠습니다.

---

C. Different Differences

https://codeforces.com/contest/1772/problem/C

• Constructive(구성적)

1부터 n까지 수 중 k개의 정수를 사용하여 강단조증가 수열을 만듭니다.

이때, [a2 - a1, a3 - a2, ... , ak - ak-1]와 같이 인접한 수의 차를 unique하게 셉니다.

인접한 수의 차를 unique하게 count한 수가 max가 되도록 하면 됩니다.

---

1부터 사용할 수 있으므로 각각에 테스트케이스에 일괄적으로 적용될 수 있는 "모범 셋"이 있습니다.

바로 [1, 2, 4, 7, 11, 16, 22, 29, 37] 입니다.

1부터 시작하여 인접 수의 차를 1, 2, 3, ... 이렇게 unique하게 가져가는 이상적인 셋입니다.

이러한 모범 셋에서 저희는 각 테스트케이스에 할당된 n과 k라는 제한을 걸어줘야 합니다.

 

우선 각각의 테스트케이스에 대해서 크기 40짜리의 색칠 가능한 배열을 만들어 줍니다.

N : 사용할 수 있는 정수의 최대 범위

K : 색칠 해야하는 횟수

 

1. 위 모범 셋에서 N보다 큰 경우는 배제하여 색칠해줍니다

break point) 물론 색칠 횟수 k가 모두 떨어지면 그만둡니다.

 

2. 위 1번을 통과하고 넘어왔다면 k - {모범 셋 크기}만큼 색칠 횟수가 남았을 겁니다.

저희는 unique한 인접 수의 차를 최대한 잃고 싶지 않으므로 맨뒤에서부터 채워나갑니다.

왜냐하면 앞에서는 촘촘하고 뒤에서는 널널하므로 뒤에서부터 색칠횟수를 최대한 다써버리는 게 좋습니다.

break point) 물론 여기서도 색칠 횟수 k가 모두 떨어지면 그만둡니다.

 

해당 수열을 출력해주면 정답입니다.

---

D. Absolute Sorting

https://codeforces.com/contest/1772/problem/D

 

• Mathematics(수학)

수열이 주어집니다. x라는 정수를 선택하여 모든 원소에 대해 |ai - x|로 대체하는 시행을 1회 진행합니다.

이 수열이 단조증가 수열이면 x를 출력, 불가능하면 -1을 출력하면 됩니다.

---

고등학교 수학시간에 절댓값 가지고 데칼코마니처럼 접으면서 놀던것이 기억나네요.

인접 수가 시행 후에 단조증가를 유지하려면 대충 중간점에서 합의보고 INF(인접 수 간 관계에 따라 부호 달라짐)까지 날려보내면 될겁니다.

각 인접관계에 대해서 부등식을 추출한 뒤 취합하면 x의 후보가 나옵니다.

 

인접 수를 두개 잡았을 때 케이스는 총 3개입니다.

a = b : 항상 단조증가를 유지합니다. 범위에 영향을 주지 않습니다.

a < b : 처음부터 단조증가 상태입니다. 하지만 과하게 x를 뺀다면 하극상이 일어날 수 있습니다.

따라서 x가 너무 크면 안됩니다. x는 중간점보다 작거나 같으면 됩니다.

a > b : 빨리 뒤집어 줘야겠네요... x를 과감하게 크게 잡아봅시다. x는 중간점보다 커야하지만 같...으면 될까요?

정확히 말하면 중간점이 정수로 나누어 떨어지지 않을 때(a+b 가 홀수일 때), 가우스로 올려줘야 합니다.

다시 말하면, a+b가 홀수일 때 x는 중간점보다 커야합니다. 짝수일 때는 같아도 무관합니다.

 

각 인접관계에 대해서 min max를 사용하여 부등식을 갱신해주면

$$ x \leq \alpha, x \geq\beta $$

형태로 나옵니다.

답을 여러개가 될 수 있으니, 후보가 있다면 x를 구하고 안되면 -1을 출력하면 됩니다.