본문 바로가기

Problem Solving/Codeforces13

Codeforces Beta Round #87 (Div. 1 Only) A. Party Simple DFS B. Lawnmower Simple DP인데, 문제에서 구하고자 하는 걸 잘 체크해야하고, 업데이트할 때 조건 잘 확인하지 않으면 틀리기 쉬움. C. Plumber 가로와 세로를 독립적으로 생각하는 것까진 좋았는데, 석환이가 준 2^k 힌트는 생각해내지 못했음. 시간이 지나고 꼭 다시 풀어봐야 함. 2016. 12. 23.
Codeforces Round #268 (Div. 1) A. 24 Game n 5일 때에 1) 홀수 : n = 5에서 끝의 (n)-(n-1)=1이고, 이걸 매번 24에 곱해주면 된다. 2) 짝수 : n = 4에서 끝의 (n)-(n-1)=1이고, 이걸 매번 24에 곱해주면 된다.B. Two Sets 2-SAT으로 해결할 수 있다. 각 원소에 대해서 A집합에 속할 때, B집합에 속할 때 서로 충돌되는 애들 사이에 간선을 준다. A 집합에만 속해야하는 경우, B 집합에만 속해야하는 경우에 대해서도 간선을 준다. SCC로 확인하고 해를 출력하면 된다.C. Hack it! g(x) : 1~x까지의 모든 f값들의.. 2016. 12. 23.
Codeforces Round #352 (Div. 1) - D. Roads in Yusland 기본적인 전략은 가장 말단에서부터 최소 가중치의 path cover를 선택하는데, 선택한 path cover가 끝이 나는 지점을 기준으로 그 밑에서부터 현재 지점을 넘어서거나 혹은 현재 지점에서부터 시작되는 path cover 중 또 가장 작은 걸 선택하는 것임. D(x) : depth가 x의 depth 이하인(x or x의 부모들을 향하는) path cover에 대해 x가 포함된 cover의 weight의 음수값(-weight). 이 커버는 x보다 같거나 더 깊은 곳에서 시작해서 최소한 x의 부모까지는 향함. [S. E]를 이미 선택했는데, S+1 혹은 그 위에서 [S, E]를 다시 또 고려하지 않기 위한 값 정도라고 생각하면 되겠다. 마치 구간에 상수 t를 더할 때, 시작점에서 t더하고, 끝점+1에서.. 2016. 6. 19.
Codeforces Educational Codeforces Round 13 - F. Lena and Queries 문제 링크 : http://codeforces.com/contest/678/problem/F 세 가지 쿼리가 주어진다. 1. 기울기가 a이고 절편이 b인 선분 삽입2. 이전에 삽입되었던 i번째 선분 삭제3. 현재 선분 집합에서 특정 x 좌표에 대한 최댓값 출력 풀이 1. - Time Limit Exceeded 쿼리를 루트개씩 묶음으로 나눔. 반평면 땅따먹기 문제에서의 부저장소-저장소 방법으로 각 묶음마다 해결함. 3번 쿼리에 대해서는 이전의 묶음들 + 현재 채우고 있는 묶음에서 답을 찾음.부저장소-저장소 컨벡스헐 트릭 방법은 이 링크에 설명되어 있다. http://codeforces.com/contest/678/submission/18520250 풀이 2. - Accepted 오프라인으로 문제를 해결함... 2016. 6. 17.
627A - XOR Equation 8VC Venture Cup 2016 — Final Round A번 문제이다. (Div.1 Edition B번, Div.2 Edition C번)별로 어렵지 않은 문제인데 한참동안 해매어서 정리.두 양의 정수 a와 b의 합이 s이고 XOR한 결과가 x일 때에, 가능한 (a, b) 순서쌍의 개수를 구하는 것이 문제이다.접근법 1)a+b = s, a^b = xb = (s-a)a^(s-a) = xs-a = a^x. 양번에 a를 XOR하면 a^(s-a) = a^x여기서 잘못됨을 깨닫고 다른 관계식을 시도함.접근법 2)a^b = a+b - 2(a&b)XOR라는 연산이 두 bit가 다르면 1이기 때문에 덧셈에서 자리올림을 빼면 그 결과가 XOR와 같다는 식.정리하면 (s-x)/2 = a&b여기서 매 digit마다 (.. 2016. 3. 10.