구사과

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일단 모든 막대기를 사용해야 하는 상황이라고 가정해보자. 넓이를 최대화하려면 모든 정점을 원 위에 뿌려주는 것이 최선이다. 직관적으로 그럴듯 해 보이긴 하는데 증명은 음.. 암튼..

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부딪힐 때 서로 방향을 바꾼다고 생각하지 않고, 서로의 번호만 바꿔서 가던 길 그대로 간다고 생각하면 복잡하지 않다. 이건 워낙 유명한 유형이니까 뭐...그렇게 하면 전체 개미의 위치는 아주 쉽게 알 수 있다. 하지만 무슨 개미가 어떤 위치에 있는지는 어떻게 알까. ..

H번 문제의 풀이를 "조속한 시간" 내에 올리겠다고 공식 홈페이지에 올라왔지만, 사실 모두의 기억 속에서 잊혀져 버린 문제이다. 그래서 아무도 작업하고 있지 않았다..얼마 전에 BOJ 즐겨찾기를 보다가 기억이 나서 풀이를 작성했다. 풀이 tex 파일과 함께 첨부한다.

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

결과본선에 진출했다. 그날 편두통이 있어서 걱정을 많이 했다. 편두통 심하면 아무 것도 못해서... 사실 대회 전에는 졸리고 편두통도 조금 있는거 같아서 거의 본선에 대해 체념 했는데, 다행히도 대회 중에 크게 컨디션 문제가 생기진 않았다. 편두통은 연휴 끝나면 병원 가서 끝을 봐야겠다. 타이레놀도 잘 안들어서 힘들다... 딱히 모난 거 없이 했던 거 같다. A B C중에서 정말 못 풀겠다 싶었던 거는 없었고, 코딩도 그렇게 시간이 오래 걸리지는 않았다. 문제는 뭐 그냥 그냥 괜찮았던 거 같은데, 그래도 얼마 전에 버추얼 돌았던 2016 R3가 훨씬 재밌었다. A. Salient StringsSuffix array가 주어졌을 때 이를 만족하는 string을 복원하는 문제이다. 처음에 잘 모르겠어서 다른 ..

Dropbox 링크