N coding

ucpc c번 구현이 극혐이긴한데 또 생각보다 별거 없기도 하다. 내가 https://www.acmicpc.net/problem/13016 문제를 푼거랑 비슷한 방식의 트리dp를 사용하면 된다. ucpc 당시에는 원래 그래프에서 트리의 지름을 하나 구하고 트리의 지름에 속하지 않는 노드를 가지고 다시 sub지름을 구해서 잘 연결해준다. 로 접근했었는데 이러면 트리에 같은 크기를 갖는 지름이 여러개 있을 경우 어떤 지름을 원래 지름으로 선택하느냐에 따라서 최대값이 이상하게 나올 수 있다. 그래서 정해는 모든 간선을 잘라본다. 이다. 근데 모든 간선을 자를때마다 subtree의 지름과 그 subtree를 제외한 나머지 트리의 지름을 구해서 연결하면 O(n^2)이 된다. 본선당시에 다들 n^2까진 생각했을 것..

타워 디펜스를 풀고나서 이 문제를 풀면 비슷하게 보인다. black인 노드를 기준으로 세로방향(위 t, 아래 f) 가로방향 (왼 t, 아래 f)의 두가지 상태를 가진다. black인 노드의 사방을 보면서 만약 위나 아래중에 하나만 존재한다면 얘는 반드시 그 하나랑 연결되야 하므로 논리식을 세워준다. (black i의 위 or black i의 위) 역시 가로방향도 마찬가지로 해준다. 만약 black i가 위에 잇는 w랑 연결이 된다면 그 w랑 연결될 수 잇는 가능성이 있는 다른 아이들은 다 연결불가이다. 그런 의미에서 w를 타고 들어가서 (black i의 아래 or black j의 ~방향)의 논리식을 세워줬다. 12345678910111213141516171819202122232425262728293031..

https://www.acmicpc.net/problem/3789 suffix array nlog n으로 짠 코드plzrun님 블로그에서 많이 참고하고 마리오블로그에서 lcp부분만 참고했다. 어떤 password가 주어졌을때그걸 왼쪽으로 1번씩 민 각각의 문자열 중에 가장 사전순으로 작은 아이의 시작 인덱스를 출력하면 된다. alabla 를 한번씩 민다면lablaaablaalblaala ... 이런식으로 총 n개가 나올 것이다이것들을 사전 순으로 정렬했을때 가장 위에 오는 문자열의 맨 처음 문자가 원래 문자열의 몇번째 애인지 출력하는 거임. 결국에는 환형이 되므로 나는 입력받은 문자열을 붙여서 2배로 늘리고가장 먼저 나오는 n보다 작은 인덱스를 출력하는데,문자열이 사전 순으로 같은 경우 인덱스가 작은 걸..