티스토리

lmlmlm

검색하기

블로그 홈

lmlmlm

lmllml.tistory.com/m

lml 님의 블로그입니다.

구독자: 8

방명록 방문하기

주요 글 목록

#16748 Colorful Tree https://www.acmicpc.net/problem/16748 집에 오는 길에 문제를 읽고 풀었는데, 난이도가 좀 높게 잡혀 있길래 나의 풀이가 정말 맞는지 끝없이 의심하며 왔다. 아무튼, 각 색에 대해서 트리의 크기를 구하는 것이다. 당연히 할 수 있는 생각이 모든 색에 대해 트리의 크기를 미리 계산해 두고, 꾸준히 업데이트 하는 것이다. 한 번에 한 색만 정보가 바뀌기 때문에 대충 가능할 것이라는 생각이 든다. X가 색이 Y가 된다고 가정하자. 그러면 그냥 나머지 Y의 색을 가진 점들 기준으로는 X를 추가하는 것과 다를게 없다. 따라서 X를 추가한다고 생각하자. X에 대해서 바로 왼쪽에 있는 걸 L, 바로 오른쪽에 있는 것을 R이라고 하자. 엄밀히 이야기하면 색이 Y인 점들 중 dfs를 하였을 .. 공감수 1 댓글수 0 2023. 10. 16.
#8202 Conspiracy https://www.acmicpc.net/problem/8202 support와 conspiracy 두 개의 그룹으로 나누어야 한다. support는 완전그래프고, conspiracy는 사이에는 간선이 없도록 해야 한다. 단상 1. 간선의 총 개수를 m이라고 하자. 그러면 support 그룹이 a명이면 sum_of_deg(support) = m + a * (a - 1) / 2 가 성립해야 한다. 혹시 이거만 성립한다면 충분한가? X = (support간 간선), Y = (support-conspiracy), Z = (conspircacy간 간선)이라면, 위 식은 다음과 같다 -> X * 2 + Y = X + Y + Z + a * (a - 1) / 2 -> X = Z + a * (a - 1) / 2 ->.. 공감수 1 댓글수 0 2023. 10. 13.
#19927 Vision Program https://www.acmicpc.net/problem/19927 H * W grid의 모든 배치에 대해서 두 black pixel의 거리가 K인지 확인할 수 있는 instruction을 만들어라 H,W, K 이거는 +만되도록 설계하면 된다. -> AND(1행, OR(2, 4, 6, 8...)), AND(2행, OR(3, 5, 7, 9...),.. 중 하나라도 1이면 행이 1 차이나는 것이고, dx[0] =1 -> AND(1행, OR(3, 4, 5, 7...)), AND(2행, OR(3, 4, 5, 7...),.. 중 하나라도 1이면 행이 2 차이나는 것이고, dx[1] =1 ->... -> 모든 항이 아니라, 모든 행에 대한 작업이라서, N이 하나 빠지기에 생각보다 횟수가 많지 않다. 위의 방법을 통.. 공감수 0 댓글수 0 2023. 10. 12.
#5250 최단 경로들 https://www.acmicpc.net/problem/5250 도로가 닫혔을 때 최단 경로의 길이를 구하여라... 특이사항 1. N = 2000이라는 점. 예상 복잡도는 O(N^2lgN)이나 O(NM)...? 2. 제거되는 경로는 최단경로인 '운 좋은 경로'에 속하는 것. 단상 1. 운 좋은 경로에 있는 모든 도시를 운 좋은 도시라고 부르자. 운 좋은 경로에 있는 모든 도로를 제거한 상태에서, 운 좋은 도시로부터의 거리를 안다고 가정해보자. 점 y의 v[x]로부터의 거리를 dist[x][y]라고 하자. distL[i][y] = min(dist[1][y] + dist[1][v[1]], dist[2][y] + dist[1][v[2]],.... ,dist[i][y] + dist[1][v[i]]) 라고 하자.. 공감수 0 댓글수 0 2023. 10. 10.
#13961 Passwords 우선 대문자 A를 입력한 것은 blacklist를 고려한다면 소문자 a를 입력한 것과 다를게 없다. 마찬가지로 0은 'o'를 입력한 것이랑 다를게 없다. 그러면 이제 dp를 돌릴 건데, 트라이 상에서 dp를 돌리면 된다 아호코라식으로 알아낸 실패함수를 고려해서 상태전이를 시켜주면 된다. 이때 소문자, 대문자, 숫자가 모두 필요하므로, 각 상태를 2^3개로 비트마스킹해서 추가로 나타내주면 된다. 아호코라식을 잘 알고 있다면 (잘 모르더라도 결과만 알고 있으면) 어렵지 않게 dp를 할 수 있다. 공감수 0 댓글수 0 2023. 6. 9.
#12917 문자열 함수 계산 만일 Suffix array와 LCP에 대한 개념이 잡혀있다면, 이 문제는 히스토그램에서 제일 큰 직사각형을 찾는 것과 거의 같다. 다만 주의할 점은 그냥 S 자체는 딱 한 번만 등장하고도 최댓값이 될 수 있음이다. 공감수 0 댓글수 0 2023. 6. 5.
#1635 1 또는 -1 처음 생각한 것은 N 차원 공간에서 수직한 평면을 찾기였는데 훨씬 간단한 관찰을 찾아버렸다. 처음의 입력 a가 어떻게 주어지든 간에 b를 이룰 N개의 수열은 다음과 같다 -> b[i] = {1, 1, ... 1, -1, -1, ...} (1이 i개, -1이 N - i개 있는 수열) pf) 어떤 수열이 b[0]와 곱했을 때 나오는 값을 k라고 하자 1) k = 0 : 그대로 b[0]과의 곱이 0이 되어버렸으니 ok 2) k != 0 : 만일 (-1, -1, ...)을 곱하면 -k가 될 것이다. 이때 b[0] ~ b[n - 1]을 진행하면 어떤 순간 0을 지나야 하니 ok N = 100으로 상수가 넉넉하니까 단순하게 M개의 수열 a에 대해 N개의 수열 b와의 연산을 하나하나 하면 된다. 공감수 0 댓글수 0 2023. 6. 5.
#5559 JOI 깃발 우선 문제에 대해서 고민해주자. 개수를 세기 위해서는 우선 겹치지 않도록 세는 것이 중요하다. 그렇기 때문에 "처음으로 JOI가 나타나는 부분"을 기준으로 dp를 해서 세야겠다는 생각을 했다. 이 dp를 어떻게 해야하는지 고민을 하다보면, 그냥 "JOI가 나타나지 않는 깃발의 수"를 세는게 더 쉬움을 알 수 있다. 일단 n, m 공감수 0 댓글수 0 2023. 6. 2.
#16160 이진 트리와 수열 https://www.acmicpc.net/problem/16160 우선 각 깊이에서 특정한 순열들이 반복됨을 알 수 있다. 예를 들어 예제의 4번째 깊이에서는 (2), (3), (1)이, 3번째 에서는 (2, 3), (1, 2), (3, 1)이 반복된다. 따라서 한 주기에서 각 순열 조각이 몇 번 등장하였는지만 세주면 k를 넘는지는 쉽게 확인할 수 있다. 다만 길이가 2^(H - depth)인 조각들을 정직하게 비교하는 것은 너무 오래 걸린다. 여기서 사실 이들이 처음 주어진 수열에서 substr(i, (1 공감수 0 댓글수 0 2023. 5. 31.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.