https://www.acmicpc.net/problem/8128증명에 증명을 더해가면서 시간 복잡도를 줄이는 스타일의 그리디였는데 재밌었다. 일단 먼저 N^2 알고리즘을 목표로 시작해보자. 가장 많은 역을 덮는 지하철 노선의 집합을 최적 집합이라고 한다. Lemma 1. 최적 집합의 모든 끝점을 리프로 변형시킬 수 있다.증명 : 그렇지 않은 최적 집합이 존재한다면 이를 두고 생각해 보자. 만약에 현재 끝점이 리프가 아니면, degree가 2 이상이라 빠져나갈 구멍이 하나 존재한다. 이 구멍으로 경로의 길이를 증가시켜나가면 답을 감소시키지 않으면서 한쪽을 리프로 만들어 줄 수 있다. Lemma 2. 최적 집합에 덮인 지하철역이 서브트리를 이루게 변형시킬 수 있다. (이 때 서브트리는 subgraph로써의..
ICPC 월드 파이널 2017 주간이 다가와서 최근 옛날 기출문제를 풀어보고 있다. World Finals 2008도 opencup 팀연습으로 돌았었는데, 문제가 좋다는 느낌은 안 들었다. 특히 어려운 문제들이 찍어 맞춰라 / 단순 코딩 지옥이라 불만족스러웠음.이번 ICPC에서 한국 팀들의 성적이 그 전과 비교가 안 될 정도로 우수하다. 어느 정도 훌륭할 것이라고 예상은 했지만 이 정도일 것이라고 예상한 사람은 아무도 없었을 것이다. 팀원들이 대부분 젊은데, 앞으로도 많은 활약을 기대해 본다. 2011 G. Magic Sticks일단 모든 막대기를 사용해야 하는 상황이라고 가정해보자. 넓이를 최대화하려면 모든 정점을 원 위에 뿌려주는 것이 최선이다. 직관적으로 그럴듯 해 보이긴 하는데 증명은 음.. 암튼..
(Stankonia, 2000)
https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명 아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다. * 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도..
문자열 S와 T가 주어졌을 때, S의 부분 문자열 중 T가 몇번 등장하는 지를 찾는 문제를 생각해보자. 예를 들어 "koosaga" 에서 "saga" 를 찾으면 "koos" != "saga", "oosa" != "saga", "osag" != "saga", "saga" == "saga" 여서 총 한번 등장하고, "aa" 를 찾으면 "ko" != "aa", "oo" != "aa", "os" != "aa", "sa" != "aa", "ag" != "aa", "ga" != "aa" 여서 단 한번도 등장하지 않는다. N = (S의 길이), M = (T의 길이) 라 하자. S[i, j] = (i번째 문자에서 j-1번째 문자까지를 포함하는 부분 문자열) 이라고 하자. 예를 들어 "koosaga"[0, 3] = "k..
http://agc013.contest.atcoder.jp/ A. Sorted Arrays단순 구현인데 코딩이 의외로 쉽지 않았다. B. Hamiltonish Path신기한 문제. path 어디에나 붙여도 되는 줄 알고 진짜 해밀턴 경로 문젠줄 알아서 좀 해멨다. 그런 경로를 아무거나 찾으면 되는 것이니 path 끝에 붙일 수 있는 정점이 있다면 무조건 붙여보는 식으로 풀면 된다. dfs로 쉽게 구현 가능. C. Ants on a Circle부딪힐 때 서로 방향을 바꾼다고 생각하지 않고, 서로의 번호만 바꿔서 가던 길 그대로 간다고 생각하면 복잡하지 않다. 이건 워낙 유명한 유형이니까 뭐...그렇게 하면 전체 개미의 위치는 아주 쉽게 알 수 있다. 하지만 무슨 개미가 어떤 위치에 있는지는 어떻게 알까. ..
시험이 끝나면 블로그 주소를 koosaga.myungwoo.kr에서 koosaga.com 으로 바꿀 예정입니다. 내부 링크 같은 것도 다 조정을 해야 해서 아마 다음주 중에 시간이 남으면 하지 않을까 싶어요...지금도 koosaga.com으로 들어오면 리다이렉션이 됩니다. 그러니까 북마크 같은 거는 일찍 바꾸셔도 괜찮습니다. + 4/24 00:40내부 링크 조정을 했습니다. 곧 반영될 예정인데, 그 전까지는 접속에 불편함이 있을 수 있습니다. 제가 실수한게 있다면 알려주세요.그리고 글 접근 기본 옵션을 번호로 줬습니다. SEO 때문에 원래 이름으로 한 것이었는데 귀찮기만 해서 그냥...
Opencup 2017 - GP of Poland
A. CNF-SAT 몰라 B. Almost pattern matching 몰라 C. Two paths http://codeforces.com/blog/entry/51228?#comment-351103 D. Mushrooms after rain strikes back몰라 E. Epic Battle alex9801 선배가 풀었다. 필요충분조건이 한정적이라 간단한 케이스 판별로 풀 수 있다고 함 F. Reachability 편의상 어떤 점들도 degree가 0이지 않다고 생각한다면, 각각의 starting point가 도달할 수 있는 정점의 개수가 구간의 형태로 나온다. starting point를 증가시키면서 가능한 다음 구간들을 모두 시도해 보면 (다음 구간은, S_i
[2017.01.25 : 처음 작성][2017.03.03 : las / pod 문제 번역 실수가 있었습니다. 죄송합니다..][2017.03.13 : klo 문제 번역 실수가 있었습니다. 죄송합니다.. 이 글은 이제 마감합니다.]https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2016/Problems폴란드어 문제만 번역합니다. Day1 ~ Day4는 영어로 문제가 나오니까 그걸로 읽으시면 됩니다.Day 5Kłódka (klo)0 이상 K 미만의 정수 배열 a[0] ... a[n-1] 이 있다. 0 이상 n-2 이하의 정수 x에 대해, 당신은 다음 두 연산을 할 수 있다. * inc(x) : a[x]와 a[x+1] 에, v
- Total
- Today
- Yesterday