http://codeforces.com/contest/816/problem/D a_1부터 a_N까지 N개의 수열이 있을 때, b_1 = a_1 + a_2, b_2 = a_2 - a_3 ... 이런 식으로 그 다음 줄에 b_n을 만든다. 같은 과정을 반복하여 수열의 수가 1개가 될 때 까지 진행했을 때 나오는 수가 뭔지 구하는 문제이다. (말보다는 그림이 이해하기 편하니 아래그림 참조) 첫번째 줄 부터 계산하다 보면 4번째 줄에 와서 규칙성을 찾을 수 있는데, 바로 이항계수이다. 구체적으로 말하면, 1번째 수열들을라 하면, 5번째 줄에 나타나는 수열들은 형태를 띈다. 즉, 첫 번째 줄에 있는 수열을 라 하면, 4줄 아래있는 5번째 줄에 나타나는 수열은 이 되고, 다시 4줄 아래에 있는 9번째 줄에 나타나는..

http://codeforces.com/contest/791/problem/B 임의의 세점 X,Y,Z에 대해 X-Y && Y-Z 이면 X-Z를 만족하는가를 묻는 문제이다. 한점 X와 연결되어있는 Xi 들은 모두 서로 연결되어있어야 한다는 것을 알 수 있고, 따라서 임의의 점 X를 잡고 그것과 연결된 노드들 X1 ~ Xk 의 개수를 k라 하면 X에 연결된 노드 개수와 X1~Xk에 연결된 노드 개수들의 합이 k*(k-1)인지를 확인하면 된다. 주의할 점은for(int i=1;i

http://codeforces.com/contest/785/problem/D 괄호문자열이 주어지면 문자열에 있는 괄호들을 임의로 선택하여 만들 수 있는 RSBS(regular simple bracket sequences)의 개수를 찾아 그 개수를 1e9+7로 나눈 나머지를 출력하는 문제이다. RSBS란 It is not empty (that is n ≠ 0).The length of the sequence is even.First charactes of the sequence are equal to "(".Last charactes of the sequence are equal to ")". 인데 간단히 말해 앞쪽은 n/2개의 '(' 뒤쪽은 n/2개의 ')'로 이루어진 괄호를 말한다. 즉 (())나 (..

http://codeforces.com/contest/782/problem/B N명의 사람들이 각각 이동할 수 있는 최대속도가 주어지고, 남/북 방향중 한쪽으로 일정한 속도로 이동할 수 있을 때 최소 몇시간(단위시간)만에 모두 만날 수 있는지를 묻는 문제이다. 속도와 거리의 범위가 1~1e9이므로 만나는 시간을 기준으로 parametric search를 시도한다. 다시말해 처음엔 k 시간동안 N명의 사람들이 이동할 수 있는 거리범위를 모두 구했을 때 만날 수 있는 장소가 있다면(교집합이 존재한다면) N명의 사람들은 늦어도 k시간 안에는 만날 수 있다는 뜻이므로 최소 시간의 범위는 1~k사이에 있게 된다. 문제에서 오차범위를 1e-6이하로 줄이라고 했기 때문에 시간의 low, hi범위의 차가 1e-7정도 ..