문제 셋 : AtCoder Grand Contest 001
AtCoder Grand Contest 001 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
3시간 동안 풀어서 총 6문제 중 A, B, C 세 문제를 풀었습니다.
A. BBQ easy
간단한 그리디입니다. 길이가 a<=b<=c<=d인 네 꼬챙이를 (a, c), (b, d)로 묶어 사용할 때보다 (a, b), (c, d)로 묶어 사용할때 더 이득이므로 정렬해두고 두 개씩 묶어서 쓰면 됩니다. 결론적으로는 정렬한 뒤 홀수번째 원소의 총합을 구하면 O(N log N)에 답을 구할 수 있습니다. 이 문제는 시작하고 5분? 정도에 풀었던 것 같습니다.
B. Mysterious Light
수학적인 문제입니다! 경로의 길이를 계산하는 방법은 여러가지가 있을 수 있겠지만, 저는 빛이 진행하면서 나오는 등변사다리꼴 별로 길이를 계산했습니다. 이렇게 계산을 하면 등변사다리꼴의 변의 길이가 두 변 길이가 서로 나눈 나머지가 되므로 유클리드 호제법과 비슷하게 O(lg N)의 시간복잡도가 보장이 됩니다. 그런데 이걸 구현을 하다보니 머릿속으로 잘 정리가 안되어 수많은 괄호 앞에서 결국 뇌정지가 와버렸습니다... 다행히 빠르게 수습해서 시작하고 1시간 정도의 시점에 해결했습니다.
C. Shorten Diameter
저는 사실 문제를 정해와 많이 다르게 풀었습니다. 두 점 사이의 거리가 K인 두 점쌍을 모두 잡아서 두 점과의 거리가 모두 K이하인 점의 개수를 세면 부분 그래프 중 지름이 K인 가장 큰 트리를 알 수 있고, 문제를 해결할 수 있습니다. 그런데 이것을 그대로 짜면 O(N^3)이 됩니다. 저는 처음에는 B에서의 뇌정지로 멘탈이 나가 두 점 사이의 거리가 K인 두 점쌍이 O(N)개라고 생각하고 이걸 그대로 짜서 한번 틀렸습니다... 거기다가 아무 생각없이 그래프를 인접행렬로 짜서 바보같이 O(N^4)의 기적의 시간복잡도를 완성하고 말았습니다. 이후 문제점을 찾고 알고리즘을 수정해 맞았습니다. 앞의 O(N^3)을 줄이는 방법은 이렇습니다. 두 점쌍을 잡고 한 점씩 잡아서 추가가 될때, 두 점과 추가가 되는 한 점사이의 쌍은 사실 당연히 다음에 기준이 되는 두 점으로 볼 필요가 없습니다. 그러므로 이것들을 체크해두고 인접한 점들의 리스트를 거리순으로 정렬해두면 문제가 풀립니다. 직관적으로 시간복잡도가 O(N^2) 정도가 되는 것 같은데 정확한 증명은 잘 모르겠습니다.... 아무튼 일반적인 풀이법으로는 지름의 중심을 기준으로 보는 간단한 O(N^2) 풀이가 존재합니다. C 해결은 시작하고 2시간 정도 시점인것 같습니다.
D. Arrays and Palindrome
팰린드롬이 되는 구간에서 서로 같아야 되는 수들끼리 선을 긋는다고 생각하면 모든 수들을 하나로 잇는 방법을 찾는다고 생각할 수 있습니다. 여기서 만들어 낼수 있는 최대 선의 수를 생각해보면 홀수 길이 팰린드롬이 3개 이상 있을 때는 전체를 연결시키는 방법이 존재할 수 없습니다. 그렇지 않은 경우에는 항상 연결을 만들 수 있는 방법이 있습니다. 그 방법은 홀수를 양쪽 끝으로 밀고 원래 배열에서 맨 앞의 길이를 1 줄이고 맨 뒤의 길이를 1 늘려 한칸씩 밀면 언제나 전체를 연결할 수 있다는 것이고 이것이 문제의 해법이 됩니다. 단, 입력으로 들어온 길이가 N 한개이면 N-1과 1이 답이 되는 예외가 존재합니다. 처음 풀때는 선을 잇는 아이디어까지는 생각해 내었으나 이후 해법을 생각해내지 못해서 해결하지 못했습니다.
E. BBQ hard
대회때는 문제만 읽고 못 풀었습니다... 나중에 풀이를 보고 풀었는데 굉장히 신기했습니다.
우선 두 팩을 고르기만 하면 고기와 야채를 꽂는 방법은 $$\binom{A_i+A_j+B_i+B_j}{A_i+A_j}$$ 로 전처리후 상수시간에 계산할 수 있음을 간단히 알 수 있습니다. 하지만 여전히 두 팩을 고르는 가짓수 때문에 O(N^2)의 시간복잡도를 가져 문제를 해결하기에는 역부족입니다. 각 팩 쌍들의 경우의 수를 빠르게 한번에 계산할 방법이 필요한데 여기서 한 가지 발상이 필요합니다. R행 C열의 격자 한쪽 꼭짓점에서 맞은편으로 최단경로를 통해 가는 경우의 수를 생각해 보면 $$\binom{R+C}{R}$$ 가 된다는것을 알 수 있습니다. 여기서 착안하여 i번 팩과 j번 팩을 골랐을 때의 경우의 수를 좌표평면상에서 (-A_i, -B_i)에서 (A_j, B_j)로 이동하는 경우의 수로 생각할 수 있습니다. 이를 이용해 이렇게 3사분면에 팩들이 위치한 점에 +1을 해주고 DP로 각 지점별로 점들에서 (+, +) 방향으로 이동해올수 있는 방법의 수를 구한 다음 1사분면에서 팩들이 위치한 지점들의 경우의 수의 합을 계산하면 모든 두 팩을 잡아 만들 수 있는 순서쌍의 결과의 합이 나오게 됩니다. 여기서 똑같은 두 팩을 써서 만들어지는 경우의 수 N가지를 계산해서 뺀 다음 순서만 뒤집힌 쌍들을 고려해 2로 나누면 답을 구할 수 있습니다. 최종 시간 복잡도는 O(팩 내용물 수의 최댓값^2)으로 계산할 수 있게 됩니다.
F. Wide Swap
작성중입니다