jwvg0425 Problem Solving

벌써부터 점점 풀기가 어려워지고 있다. 14446. Promotion Counting 15899번 문제와 완전히 똑같은 문제. 이제는 너무 널리 알려진 테크닉이 아닌가 싶다. 일단 오일러 투어 테크닉을 써서 트리를 배열로 펴주고 나면 각각의 서브트리를 구간으로 나타낼 수 있다. 이제 이 구간에서 루트의 값 x보다 큰 원소의 개수를 세는 문제가 되는데, 이는 여러 가지 자료구조를 이용해서 풀 수 있다. 나는 그냥 머지소트 트리 써서 풀었다. 14522. Modern Art(Platinum) 문제를 잘못 읽어서 약간 헤맸다. N^2개 수를 각각 최소한 한 번씩 쓴다는 조건이 있는데 이것 때문에 생기는 예외를 처리를 안 했음. 우선 각각의 색에 대해 그 색이 칠해진 사각형 영역의 크기를 구한다. 이 사각형 영..

USACO 플래 문제 밀기를 하고 있다. 쉬운 난이도부터 정렬해서 푸는 중. 11979. Fort Moo 부분합을 구해두면 O(N^2M^2)은 쉽게 생각할 수 있다. 사각형을 이루는 네 꼭지점을 정한 뒤 그 네 변의 어디에도 X 표시가 없으면 답을 갱신해주는 걸 반복해주면 되기 때문. 여기서 N 혹은 M을 하나 떼면 시간 안에 돌아가는 시간 복잡도가 된다. 좌우 부분합, 상하 부분 합은 세제곱 베이스로 계산이 가능하기 때문에 부분합까지는 똑같이 구한다. 사각형의 위아래 변만 고정하면 O(N^2)이 되는데, 여기서 윗변과 아래변을 연결하는 X 자 표시가 없는 직선의 위치는 부분합을 이용하면 O(M)에 전처리가 가능하다. 이렇게 구해놓은 각 직선끼리 최대한 윗변 or 아랫변에서 X가 없는 조건을 만족하면서 ..

5 solve 패널티 703min, 28등으로 종료했다. 올해는 PS 관심 있는 초심자 두 분 대리고 팀 대회 경험 + 연습 시켜드린다는 느낌으로 참여해서 성적은 크게 생각 안 했는데, in30 했으니 성적도 나쁘지 않게 잘 마무리한 것 같다. in50을 목표로 했는데 훨씬 초과 달성. 본선에서 각각 한 문제씩은 풀게 해드리고 싶었는데 이것도 충족해서 깔끔하게 잘 끝난 것 같다. 아래는 타임라인별 정리. 다른 두 팀원분은 각각 대회 신청 당시 이름인 51호관114호 / 나무둥지 로 지칭해서 썼다. ~00:15 문제를 쭉 읽고 간단하게 풀이를 생각했다. A는 읽고 대충 풀이 방향이 생각은 났는데, 좀 더 쉬운 문제가 있을 것 같아서 일단 내버려두고 다른 걸 봤다. 근데 더 쉬운 문제가 없었다.. ㅋㅋ 다른..

안타깝게도 서버가 터지는 바람에 마라톤 대회같은 형식으로 진행됐다. 문제가 전반적으로 퀄리티가 높았고 재밌었는데 예기치 못한 사고로 인해 정상적으로 운영되지 못한게 안타깝다. 4문제만 풀면 본선 진출이었지만 그래도 최대한 열심히 문제를 푸는게 출제자 분들에 대한 예의일 것 같아 최대한 열심히 풀었다. 그리고 전반적으로 문제가 꽤 어려웠던 것 같은데 다들 굉장히 잘 풀어서 놀랐다. 확실히 사람들의 평균적인 실력이 많이 높아졌다는게 체감된다. 딱히 시간 제한이 없었던 대회라(+4solve만 하면 통과였다보니) 스코어보드가 딱히 의미가 있는 것 같지는 않지만, 아무튼 시간 중에는 7솔브 29등으로 예선을 통과했다. 아래는 내가 푼 예선 문제들을 난이도 순으로 정리해 본 것. A. 수학은 비대면 강의입니다. 단..

ttps://mao.snuke.org/tasks/32 Problem 0032 - Log Run Stop Step Reset Submit mao.snuke.org 처음 생각은, o -> 0, 00 -> 1, 11 -> 2, ... 를 연쇄적으로 적용시키는 것이었다. 이렇게 연쇄적으로 적용시킨 다음에 남은 부스러기들을 지우면 해결이 된다고 봄. 그 생각을 충실히 옮겨서 20줄로 해결했다. o:0 00:1 11:2 22:3 33:4 44:5 #0:0_ #1:1_ #2:2_ #3:3_ #4:4_ #5:5_ _0:_ _1:_ _2:_ _3:_ _4:_ _5:_ _:: :# 근데 생각을 해보니, 00:1, 11:2 이렇게 합칠 필요가 없이 필요한 o 개수를 직접 나열하면 수 + o 의 조합으로 환원되게 만들 수 있..

https://mao.snuke.org/tasks/25 Problem 0025 - Balanced Statement You are given S contains only '(', ')'. Replace it with "yes" if it is correct parenthesis sequence, "no" otherwise. Correct parenthesis sequences are defined as follows. * An empty string is a correct parenthesis sequence. * If string A is a cor mao.snuke.org 모든 올바른 쌍을 먼저 제거하고 나면, (((( 꼴이거나 ))))) 꼴이거나 ))))((((( 꼴이 된다. 그래서 이 각각의 경우..

https://mao.snuke.org/tasks/10 Problem 0010 - Increment Run Stop Step Reset Submit mao.snuke.org 맨 처음에는 제일 간단한 생각부터 시작해서 짰다. 커서 하나 만들고 -> 맨 끝으로 옮기고 -> 맨끝에서 값 1 올리고 -> 그게 2가 되면 앞자리 1증가시켜주고 -> 반복. _0:0_ _1:1_ 0_::1 1_:2 02::10 12:20 2::10 :_ 그래서 이렇게 짰다. 8 라인. 조금 생각해보니, 2를 별도로 처리할 필요가 없을 것 같아 이 부분을 묶어서 처리하게 바꿨다. 커서를 맨 오른쪽으로 보내고 -> 보낸 다음 해당 커서를 +1을 나타내는 형태로 변경(_). 0_ 이 나오면 1로 바꾸고, 1_이 나오면 _0 으로 바꾸는 ..

https://mao.snuke.org/ Markov Algorithm Online Markov Algorithm quote from wikipedia: The Rules is a sequence of pair of strings, usually presented in the form of pattern → replacement. Each rule may be either ordinary or terminating. Given an input string: Check the Rules in order from top to bottom mao.snuke.org Markov Algorithm으로 문제를 푸는 사이트인데, 룰이 굉장히 단순하면서도 재밌다. 문제를 풀면서 재밌었던 포인트들을 까먹지 않게 기록해두..

https://www.acmicpc.net/problem/16663 16663번: Distance Sum You are given a connected undirected unweighted graph. The distance d(u, v) between two vertices u and v is defined as the number of edges in the shortest path between them. Find the sum of d(u, v) over all unordered pairs (u, v). www.acmicpc.net 문제 요약 연결된 가중치 없는 무향 그래프가 주어진다. $ d(u,v) $ 를 정점 $u$와 $v$ 사이의 최단 거리라고 할 때, 모든 $(u, v)$ 쌍에 대해 $..

와! 다 풀었다! 역시 뭔가 조금 더 생각하면 풀리는 거였는데 생각이 조금 모자라서 못 풀었던 것 같다. 전체적으로 좀 더 빨리 + 정확하게 풀어야하는데 여전히 그게 잘 안 되는 듯. 아래는 이 문제들을 한 방에 못 풀고 2차 시도에서야 풀게 된 이유 정리 A(2100, 26분) 이 문제는 그냥 간단한 케이스 분류 + 구현 문제인데 1-3 연습에서 다른 문제 푸느라 풀 시간이 없어서 못 풀었다. 푸는데 시간이 좀 걸리긴 했지만 꽤 엣지 케이스가 많은 문제인데 한 방에 맞아서 그래도 잘 푼 것 같다. B(2200, 43분) 이 문제는 1-2 연습에서 한참 붙잡았는데 못 풀었던 lazy propagation 문제였다. 그 때 못 풀고 이번에도 또 한참 고생하다 풀었는데, 내가 애초에 식 유도를 좀 잘못했다는..