구사과

http://wcipeg.com/problem/ccc14s2p3 문제에서 주어지는 명령들을 CNF 형태로 해석해보자, 1 -> 늑대인간, 0 -> 시민이다. D a b => a -> b A a b => a -> ~b CNF 형태가 유용한 점 중 하나는 그래프 이론적인 해석이 가능하다는 것이다. (예를 들어 2-SAT은 도달 가능성 == clause의 모순 여부라는 점을 활용한다.) 여기서 특히 주목할 점은 문제의 조건 대로라면 이렇게 주어진 명령을 그래프화 했을 때 트리 (사실은 포레스트) 형태의 모습이 생긴다는 것이다. 여기서는 늑대인간의 수가 K개인 경우의 수를 묻기 때문에, 이제 조건을 만족하는 경우의 수를 셀 때 트리 DP를 사용하면 된다. 트리 DP를 사용한다 하면 당장 rough하게 떠오르는 ..

This is my problem solving log during my IOI training camp.It will not cover all of my camp problem, I will just list some interesting ones. Since I'm lazy enough to install Korean IME in Ubuntu, this log will be written in English. Day 1Game Strategy (WF 2014)https://www.acmicpc.net/problem/10053think backward. Buffed Buffet (WF 2014) https://www.acmicpc.net/problem/10051Didn't have enough time..

[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)는 이 정점으로 들어오는 간선..