[코드포스] Round #812 (Div. 2)

안녕하세요 aim_higher 입니다.

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

---

A. Traveling Salesman Problem

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

• Implementation(구현)

 

좌표평면 위에서 (0, 0)부터 스타트해서 주어진 점들을 찍고 다시 (0, 0)로 돌아와야 합니다.

이때, 주어지는 점은 x축 위거나 y축 위로만 주어진다고 합니다. (다행)

문제에서 요구하는 조건에 만족하기 위해서 총 소요되는 이동 수를 출력하면 됩니다.

---

(0, 0)으로 부터

왼쪽으로 가장 먼곳, 오른쪽으로 가장 먼곳

위쪽으로 가장 먼곳, 아래쪽으로 가장 먼곳

의 거리를 다 더해서 2를 곱하면 됩니다.

 

왜냐하면 해당 위치로 갔다가 다시 그만큼 와야하기 때문입니다.

---

B. Optimal Reduction

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

• constructive (구성적)

수열 a가 주어집니다. b는 수열 a의 순서를 고려한 순열입니다.

즉, 수열 a는 순열 b에 포함되어 있는 하나의 수열인 겁니다.

 

이때, 수열 내 원소를 모두 0으로 만들기 위해 다음과 시행을 할 수 있습니다.

아무 범위나 잡고 다같이 1씩 줄이기 입니다. (범위를 제자리로 잡아도 가능합니다)

위의 시행을 최소한으로 진행하여 0으로 만든 값을 f(x)라고 합니다.

 

최종적으로 모든 순열에서 f(a) <= f(b)이 만족하는지 출력하면 됩니다.

즉, 수열 a가 순열 중에서 베스트 시나리오인지 묻는 겁니다.

---

구성적 문제니까 약간 직관으로 접근하셔도 됩니다.

수열이 가운데가 볼록하고 양쪽으로 완만한 산이라고 생각해보세요.

그래야 "범위에 적용되는 시행"을 최대한 전체에 적용하면서 좁혀나갈 수 있겠죠?

 

그렇다면 a 수열이 "산"인지 판명하시면 됩니다.

물론, 반쪽짜리 산이여도 가능합니다.

이렇게 접근하시면 쉽게 정답을 찾을 수 있습니다.

---

C. Build Permutation

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

• constructive (구성적)

다음에 풀게요...!!