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으로 문제를 푸는 사이트인데, 룰이 굉장히 단순하면서도 재밌다. 문제를 풀면서 재밌었던 포인트들을 까먹지 않게 기록해두..
[16663] Distance Sum
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)$ 쌍에 대해 $..
training 2-1
와! 다 풀었다! 역시 뭔가 조금 더 생각하면 풀리는 거였는데 생각이 조금 모자라서 못 풀었던 것 같다. 전체적으로 좀 더 빨리 + 정확하게 풀어야하는데 여전히 그게 잘 안 되는 듯. 아래는 이 문제들을 한 방에 못 풀고 2차 시도에서야 풀게 된 이유 정리 A(2100, 26분) 이 문제는 그냥 간단한 케이스 분류 + 구현 문제인데 1-3 연습에서 다른 문제 푸느라 풀 시간이 없어서 못 풀었다. 푸는데 시간이 좀 걸리긴 했지만 꽤 엣지 케이스가 많은 문제인데 한 방에 맞아서 그래도 잘 푼 것 같다. B(2200, 43분) 이 문제는 1-2 연습에서 한참 붙잡았는데 못 풀었던 lazy propagation 문제였다. 그 때 못 풀고 이번에도 또 한참 고생하다 풀었는데, 내가 애초에 식 유도를 좀 잘못했다는..