구사과

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

APIO 2015 작성중인 지금 시간은 토요일 오후 8시. NDA가 있어서 공개는 좀 늦을듯. A : 만들어 놓을 값을 정해놓은 후 (parametric 엇비슷) dp를 돌리면 된다. APIO 역대 문제를 감안하면 제일 쉬웠던 문제인듯. 섭테 케이스 나눠서 짜게 한거 뭐 이해는 간다만 좀 별로였다. (C번도 그런 식이긴 하지만 뭐..) 여담으로 아무 생각없이 짜서 아직 내 풀이가 왜 되는지 모른다. 그냥 어셉먹기에 그런 줄 알았다. B : N^2 다익스트라 + NM 그래프 생성으로 57점 긁었다. 개인적으로 그 57점이 이번 대회 가장 쉬운 섭테였다. N = 30000은 풀이가 정말 다양했다. 내가 본 복잡도가 N^1.5 / N^1.5lgN / Nlg^3M / N^2 (...) 인데 N^2 커팅은 AC고..

당시 대회에서 실제로 맞닥뜨린 문제인데, 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를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..

http://ppss.kr/archives/38156 사람들에게는 아무리 옳은 소리라도 일정한 자격을 부여받은 사람만이 그 말을 할 수 있다는 모종의 신화가 있다. 그래서 학벌이 좋지 않은 사람들은 대개 학벌에 대해 말하는 행위 자체를 부끄러워한다. 사회 운동을 하거나 어릴 적부터 공부 외적인 길로 진로를 틀었던 경우가 아닌 이상 거의 그렇다. H의 예시를 들며 내가 말하고 싶은 바는 두 가지다. 첫째는 학벌 소속감이 구성원들의 의식 체계를 지배한다는 것이다. 누구나 아는 이야기지만, 환기해보자는 의미다. 둘째는 학벌에 관한 한, 대부분의 사람들은 고아원에서 자란 소녀 주디와 비슷한 처지라는 것이다. 대부분의 사람들은 자신의 학벌 반경 바깥에서 어떤 일이 벌어지고 있는지 전혀 알지 못한다. H처럼 독특한..