8/2 연습

5485. 평균값 수열 (IOI '05)

http://icpc.me/5485

이 문제에서 가장 중요한 아이디어는 \(s_1\)과 \(m_1 \cdots m_{n-1}\)만으로 \(s_2 \cdots s_n\)을 결정할 수 있다는 것이고, 따라서 가능한 수열의 개수는 가능한 \(s_1\)의 개수와 같다는 것이다.

수열의 단조 증가 조건으로부터,

\(s_2 = 2m_1 - s_1 \ge s_1 \Rightarrow s_1 \le m_1\)

\(s_3 = 2m_2 - s_2 \ge s_2 \Rightarrow s_1 \ge 2m_1 - m_2\)

\(s_1 \le 2m_1 - 2m_2 + m_3\)

\(\vdots\)

와 같이 \(s_1\)에 관한 총 \(n-1\)개의 부등식을 얻을 수 있고, 이를 통해 \(s_1\)의 상한과 하한을 잘 좁혀서 그 범위 내에 있는 수의 개수가 답이 된다. 그런데 졸렬하게도 메모리 제한이 16MB라서 그냥 배열에 \(\{m_i\}\)를 담으면 MLE가 난다... 그때그때 \(m_i\)를 입력받아 처리하는 방식으로 \(O(1)\)메모리에 처리하도록 하자.

Time Complexity : \(O(N)\)

Space Complexity : \(O(1)\)

---

1007. Vector Matching

http://icpc.me/1007

본격 백준 접게 되는 문제

1006번 [습격자 초라기]가 까다로운 처리의 끝판왕으로써 백준을 접게 만든다면, 이 문제는 (약간의) 아이디어를 요구하는 최초의 문제. 

사실 벡터를 정말로 두 개씩 짝지어서 구하려면 총 경우의 수가 \(\frac{20!}{10! \cdot (2!)^{10}} \sim 6.5 \times 10^8\)이 되어서 당연히 TLE가 난다. 여기서 생각해 볼 점은 임의의 두 점 \(A, B\)에 대해서 \(\vec{AB}\)는 \(\vec{OA}-\vec{OB}\)로써 나타낼 수 있다. (\(O\)는 원점) 그래서 결국 이 문제는 \(N\)개의 위치벡터 \(\vec{OA_i}\)에 대해서, \(N/2\)개에는 +부호를, 나머지 \(N/2\)개에는 -부호를 붙여 다 더한 벡터의 크기를 최대화하는 문제이고, 이는 시간복잡도 \(O(_{N}{C}_{N/2})\) 안에 해결할 수 있다. 재귀함수 쓰기 귀찮아서 비트마스크를 썼는데, 그래도 AC는 난다...

Time Complexity : \(O(2^N + N\cdot_{N}C_{N/2})\)

(정해 : \(O(_NC_{N/2})\))