업그레이드 평소 게임을 즐겨하는 종현이는 이번에 자신이 하던 게임에 “아이템 업그레이드” 시스템이 도입되어 이를 이용해 보려 한다. 종현이는 N개의 서로 다른 아이템을 가지고 있고, 이 아이템들은 모두 1부터 M단계까지의 등급이 존재한다. 아이템을 업그레이드에 필요한 강화석을 한 개 사용하면 아이템의 등급이 1만큼 증가한다. 즉, i등급의 아이템에 강화석을 한 개 이용하여 업그레이드하면 i+1등급이 된다. 강화석을 사용하면 아이템은 무조건 업그레이드가 되지만, 만약 어떤 아이템이 M등급이라면 이미 최고 등급이기 때문에 더 이상 강화석을 사용할 수 없다. 종현이는 최대 M등급까지 존재하는 서로 다른 N개의 1등급 아이템을 가지고 있을 때, K개의 강화석을 모두 사용하여 만들 수 있는 아이템 등급의 경우는 ..

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번째 줄에 나타나는..

유적지 여행 유근이는 N개의 도시와 M개의 도로로 연결된 유적지를 여행하려고 한다. 유근이는 사실 도시를 방문하는 것 보다 드라이브하는 것에 더 관심이 많아서 N개의 도시를 모두 방문하지 못하더라도 M개의 도로를 모두 지나가길 원한다. 다만 유근이는 M개의 도로 중 2개의 도로는 한번씩만 지나고, 나머지 M-2개의 도로는 정확히 2번씩 방문하는 여행루트를 만들려 한다. 도로로 연결되어있지 않은 곳은 서로 이동할 수 없기 때문에 한 번 여행을 시작하면 시작점과 연결된 도시들만 여행할 수 있다. 또한 여행 루트에서 출발지와 목적지 도시는 중요하지 않고, 어떤 도로를 한번씩만 지나는지, 어떤 도로를 두 번씩 지나는지에 따라 각기 다른 루트로 간주한다고 한다. 유근이가 모든 M개의 도로를 여행할 수 있는 여행루..

http://hongjun7.tistory.com/64

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정도 ..

https://www.acmicpc.net/problem/6591 정답이 int범위 안에 들어온다는 힌트가 주어진 Combination을 구하는 문제이다. 파스칼의 삼각형을이용한 DP로 접근을 하면 n = k = 2^(31)-1 인 경우도 있기 때문에 배열자체를 잡을 메모리가 부족하다. (DP배열을 벡터로 짜보면 될것같기도한데.. 해보진않음) 간단하게 정말 조합을 구하는 손으로 구하는것처럼 계산하면 overflow없이 계산할 수 있다. 먼저 r>n/2인경우에 r=n-r로 바꿔준다. (∵ nCr = nC(n-r)) r>0인 경우만 생각해보면, n/2>=r 이고, r>0므로 (n-r+1) >= (r+1)/r > 1 을 만족한다. 따라서 (n-r+1)/r > 1 이고, nCr < 2^31 이므로 nC(r-1)..

http://codeforces.com/contest/779/problem/A 1~5까지의 성적을 가진학생들이 두 반에 무작위로 속해 있을 때 최소한 몇번의 학생교환을 하면 두반에 속해있는 학생구성이 같게되는지를 묻는 문제이다. 학생구성이 같다는 뜻은 1점부터 5점까지 받은 학생의 수가 두 반에 동일하게 분포되어있는 상태를 말함. 일단 두반에 동일하게 분포시킬 수 없는경우는 두 반에 속해있는 1점부터 5점들의 학생수를 세어보았을때 하나라도 홀수명인 점수가 있는 경우이다. 이 경우를 제외하곤 무조건 동일하게 분포가 가능하다. 각 반에 있는 점수대별로 인원을 체크 한 후, 더 많은 인원/2명을 상대방 반으로 넘기는 식으로 계산을 해주면 해결할 수 있다.

https://www.acmicpc.net/problem/9426 예전엔 중앙값 관련 문제 풀때 PQ 2개를 두고 풀거나 (최대/최소 중앙값을 찾는경우)parametric search로 풀었던것 같은데 오랜만에 중앙값 문제를 봐서 그런지 전에 풀었던 풀이가 기억이 나지않아 좀 다른 방법으로 풀었다. counting을 체크하는 리프노드가 65536개 짜리인 indexed tree를 구성하고, 최초 k개의 입력된 숫자를 indexed tree에 update한 뒤 중앙값인(k+1)/2번째 숫자가 어디있는지를 indexed tree에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다. 마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식..