엣코더 ARC 142 풀이

https://atcoder.jp/contests/arc142/tasks/arc142_a

A - Reverse and Minimize

K를 리버스한 것이 K보다 작으면,

K는 애초에 f(x)의  값이 될 수 없으니 0을 리턴합니다.

K와 reverse(K)에 10배씩 곱하며

N보다 작을 경우엔 값을 추가합니다.

K=reverse(K)인 예외에 주의합니다.

 

https://atcoder.jp/contests/arc142/tasks/arc142_b

B - Unbalanced Squares

 

체스판마냥 나눈 뒤, 값을 절반으로 나눈 후

백색 -> 작은 수부터 차례대로 채우기

흑색 -> 큰 수부터 차례대로 채우기

를 하면 답이 나오는 것을 확인했습니다.

 

왜 그런지는 증명... 을 해봐야 알 것 같습니다만.. 값을 완전히 나누어서 뿌리니 불균형이 일어나서 조금씩 최대값과  최소값의 개수가 작은 것 같습니다.

 

https://atcoder.jp/contests/arc142/tasks/arc142_c

C - Tree Queries

1번 인덱스에서 2를 제외한 다른 모든 인덱스까지의 거리를 일단 쿼리합니다.

마찬가지로 2번 인덱스에서 1을 제외한 다른 모든 인덱스까지의 거리를 쿼리합니다.

 

주어진 것은 트리이므로, 1과 2를 펴면 직선으로 볼 수 있습니다.

 

이 1과 2 사이에 노드가 있는 경우, 1 - 노드 - 2 가 곧 거리입니다.

그러므로 구했던 거리들을 각각 노드별로 더한 다음, 최소값을 구하면 일반적으로 궈리입니다.

 

이때 예외는, 1과 2 사이에 노드가 없는 경우입니다. 이러면 최소값이 3이 됩니다.

 

이는 1과 2 사이에 노드가 2개 있을 때와 구분하기 어렵기 때문에 추가적으로 쿼리해 주어야 합니다.

 

1과 2 사이에 노드가 2개 있으면, 그 노드들의 최소값은 모두 3입니다.

각 노드 사이의 거리를 쿼리한 후, 1이 나오면 1과 2 사이에 노드가 2개 있는 것이므로, 3을 리턴합니다.

그렇지 않으면, 1을 리턴합니다.

 

D, E, F는 풀지 못해 이후 풀이를 작성할 예정입니다.