구사과

[5/13 초본, 5/27 L 추가, 5/28 M 추가, 6/22 I,J 추가, 6/23 N,T 추가] 흔한 DP 컨테스트라고 말은 하지만, 어렵다.http://tdpc.contest.atcoder.jp/ ASubset Sum이라는 유명한 문제로, 풀이 역시 유명하다. 개행 문자를 넣어야만 AC가 되니 유의.cpp : http://codepad.org/nKJbfaBR Cwin[player][i] 를 i번째 라운드까지 진행되었을 때 player의 승률이라 정의하자. 동적 테이블을 채울 때, 각 플레이어가 i-1번째 라운드를 통과하고 본인과 대전할 확률을 구할 수 있으며, 싸워서 이길 확률은 식으로 주어져 있다. 이를 통해서 테이블을 채울 수 있으며 1초 안에 통과될 만큼 시간복잡도가 나올 듯 하다. 사실 ..

https://www.acmicpc.net/problem/1200 Naive하게 하면 (n-1)Cr * (m-1)Cs 정도의 시간에 풀 수 있으며 당연히 TLE가 난다. ( 상한이 O(2^(n+m) 이다.) 그럼에도 n과 m이 작은 편이라 지수를 하나 정도만 날려도 될 거 같은 범위이다.. 실제로 그렇고. 일단 한가지 축으로 배열을 미리 잘라놓고 생각을 하면, 이는 여러개의 1차원 배열을 자르는 문제로 환원이 된다. 배열은 (s+1)개 나올 것이며, 이를 구간 [1,a1] , [a1+1,a2] ... [as+1,n] 으로 자르는 것이라고 생각하면, Max(1

https://www.acmicpc.net/problem/10454 Observation 1. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 세 정사각형으로 채울 때, 세 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. 케이스를 많이 나누는 식으로 증명이 되지 않을까.. 싶다. Observation 2. 모든 정점을 포함하는 최소의 직사각형을 가정하자. 이를 두 정사각형으로 채울 때, 두 정사각형 중 하나는 그 직사각형의 모서리를 모서리로 가지고 있다.-> 역시 그렇지 않게 정사각형을 열심히 그려보면 (...) 알 수 있다. Observation 3. X가 3SQ-sufficient 일때 X+1은 3SQ-suf..

https://www.acmicpc.net/problem/96612^k 일때의 풀이를 보고 꽤 고민하다가 풀었다. 내가 머리가 안 좋은갑다... N >= 5 이상일 때는 상대가 어떠한 전략을 쓰더라도 modulo 5 값을 같게 만들 수 있다.N = 1, N = 3, N = 4일 때는 어떠한 전략이어도 상근이가 이긴다.N = 0, N = 2일때는 어떠한 전략이어도 창영이가 이긴다. 고로 입력을 받은 후 모듈러에 따라 저 결과를 출력해주면 된다.

https://www.acmicpc.net/problem/2543 Interval Graph에서의 Vertex Cover의 개수라는 말로 이 문제를 한줄요약할 수 있다. 하지만 말하는 그대로 dp를 짜기에는 상황이 너무 복잡하다. dp가 애초에 되는지 잘 모르겠다. 여기서 Vertex Cover의 정의를 잠깐 훑고 가자면 "그래프의 모든 간선에 대해, 최소 1개의 정점이 집합 S에 속하도록 하는 정점의 부분집합 S" 이다. 때문에 S의 여집합 I는 "그래프의 모든 간선에 대해, 최대 1개의 정점이 집합 I에 속한다" 라는 성질을 만족한다. 즉 I는 그래프의 독립 집합이다. 즉 Vertex Cover의 여집합은 Independent Set이라는 것을 알고 있으면 이 문제를 풀 수 있다. Interval G..

당시 대회에서 실제로 맞닥뜨린 문제인데, O(NlgN) 풀이에 꽤 근접했지만 (ㅠㅠ) 결국 제대로 된 풀이를 만드는 데 실패하고 O(N^2lgN) 의 풀이를 짤 수밖에 없었다. 문제는 상당히 단순하다. 이것저것 description이 복잡하게 들어와 있지만 요약하자면 K = 1인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 |Ai - X| + |Bi - X| 를 최소화 하는 X를 찾으면,K = 2인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) 를 최소화하는 X,Y를 찾으면 된다. K = 1인 경우는 쉬운 그리디 알고리즘이 존재한다. 2N개의 원소가 들어있는 A + B 집합에서의 N번째 원소가 답이다. 복잡도는 O(NlgN) ..

https://www.acmicpc.net/problem/9495 혼자 못풀고 결국 풀이를 봤는데, 풀이가 상당히 멋져서 소개. 득점을 하는 방법을 쭉 따져보자.1. 절대 'x'로 득점을 할 수 없다.2. 'o'로 득점을 하려면 주위에 있는 '.' 들은 모두 차있어야 한다. 즉 주위에 있는 '_'에서 득점할 수 없다.3. '_'로 득점을 하려면 주위에 있는 'o' 들은 모두 차있어야 한다. 즉 주위에 있는 'o' 에서 득점할 수 없다. 벌써 답이 나왔다. 인접한 'o' - '.' 쌍을 모두 이었을 때의 최대 독립 집합 정점 수 를 계산하면 이 문제를 풀 수 있다. degree가 0인 'o'는 없음이 문제 조건에 있으며, '.'는 그냥 넣어줘도 무방하다.새롭게 생기는 그래프는 일단 격자 그래프의 subgr..

https://www.acmicpc.net/problem/1210 1. 최소 코스트 구하기 문제를 뒤집어서 에지를 막을 때 일정한 코스트가 든다고 가정한다면, 이 문제는 Minimum Cut이라는 유명한 문제로 바뀐다는 것을 알 수 있다. Minimum Cut은 Maximum Flow와 동치임이 잘 알려져 있으므로 이러한 문제는 쉽게 풀 수 있다. (http://koistudy.net/?mid=prob_page&NO=1236)다만, 애석하게도 이 문제에서는 정점을 막을 것을 요구하고 있기 때문에 이것만으로는 안 풀린다. 하지만 약간의 변형을 거치면 이 역시 Minimum Cut을 사용해서 쉽게 풀 수 있다. 정점을 In(i), Out(i)라는 두 정점으로 분할하자. In(i)는 이 정점으로 들어오는 간선..

이번 라운드는 할말이 별로 없는듯.. 푼 순서대로 서술한다 A 이 라운드가 dynamic scoring 인줄 몰랐다 맨 처음엔. 내가 너무 싫어하는 lexicographical + bracket 의 연속이라 정말 풀기 싫었는데 5분만에 E번을 푸는 사람이 나오면서 아 이거 dynamic scoring이구나를 깨닫고 던졌다. 결국 라운드 끝날 때 A가 가장 어려운 문제로 확인. 솔직히 딱 봐도 어려워 보인다. E 5분만에 AC가 나와서 아 저거 복붙충 아니냐 **.. 은 농담이고. 쉬운가 싶어서 바로 봤다. (다만 3~5분 AC는 복붙이 맞는 거 같다) 처음 문제를 봤을때는 풀수 없음을 증명하는게 빠르지 않을까 (...) 하고 당황했는데 제약 조건을 본 후 그냥 평이하게 풀리는 문제임을 확인했다. 20분 ..

http://poj.org/problem?id=2104https://www.acmicpc.net/problem/7469 1. Naive - O(MNlgN)더 이상의 자세한 설명은 생략..O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ; 2. Query Sorting - O(NlgN + M*N^0.5*lgN)http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4때문에 역시 자세한 설명은 생략.간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..