Codeforces Round #318 div2
http://codeforces.com/contest/574
A
제일 처음 숫자보다 크거나 같은 숫자가 없을때까지 나머지 숫자중에 제일 큰수에서 1을 감소시키고 제일 처음숫자에 더해주고 답을 갱신하면 된다. 숫자 하나 업데이트하고 나서 다시 처음부터 보지 않고 그냥 뒤에 쭉 봤더니 WA, 그래서 우선순위큐를 써서 없을때 까지 돌렸다.
A는 틀리지 말자 ㅜㅜ
B
DFS로 cycle 길이 재는 문제를 접했던 적이 있어서 DFS로 길이 3인 cycle을 찾으려고 시도하였으나 계속 WA가 떴다. 너무나 당연히 된다고 생각했었는데 마침내 예외 케이스를 찾아냈고 안된다는걸 알았다(DFS에 대해 좀 더 깊이 파봐야겠다.). 그리고 그냥 단순하게 4000*4000 인접행렬 만들어 풀었다.. 메모리 제한 넉넉할땐 걱정하지 말고 잡자.
C
2랑 3밖에 못곱하므로 결국 어떤 두 수가 같으려면 소인수분해 했을때 2와 3를 제외한 나머지 부분이 같아야 된다. 그래서 2로 안나눠질때까지 나누고 3으로 안나눠질때까지 나눈뒤에 비교 하면 된다. 쉬움.
D
어떤 줄이 사라지는 시간은 왼쪽이 사라지는 시간 + 1, 오른쪽이 사라지는시간 + 1, 자기 높이 중 최소라는 사실은 알아냈으나 이후에 어떤식으로 접근해야 할지 방법이 떠오르지 않았다. DP로 풀면 된다고 하는데 아직 자세히 보지 않아서 모르겠다.
..editorial의 풀이는 와닿지가 않았는데 밑에 보니 dijkstra 풀이가 가능하다고 하더라. 각 블록들을 노드로 생각하고 가상의 소스노드에서 블록의 높이를 가중치로 가지는 간선을 연결한다. 인접한 블록들에 대해서는 가중치 1의 간선을 만들어 준다. 최종 답은 소스에서 다익스트라를 돌렸을때 최단거리가 가장 긴 노드까지 가는 거리가 된다.
E
모르겠다.
A
제일 처음 숫자보다 크거나 같은 숫자가 없을때까지 나머지 숫자중에 제일 큰수에서 1을 감소시키고 제일 처음숫자에 더해주고 답을 갱신하면 된다. 숫자 하나 업데이트하고 나서 다시 처음부터 보지 않고 그냥 뒤에 쭉 봤더니 WA, 그래서 우선순위큐를 써서 없을때 까지 돌렸다.
A는 틀리지 말자 ㅜㅜ
B
DFS로 cycle 길이 재는 문제를 접했던 적이 있어서 DFS로 길이 3인 cycle을 찾으려고 시도하였으나 계속 WA가 떴다. 너무나 당연히 된다고 생각했었는데 마침내 예외 케이스를 찾아냈고 안된다는걸 알았다(DFS에 대해 좀 더 깊이 파봐야겠다.). 그리고 그냥 단순하게 4000*4000 인접행렬 만들어 풀었다.. 메모리 제한 넉넉할땐 걱정하지 말고 잡자.
C
2랑 3밖에 못곱하므로 결국 어떤 두 수가 같으려면 소인수분해 했을때 2와 3를 제외한 나머지 부분이 같아야 된다. 그래서 2로 안나눠질때까지 나누고 3으로 안나눠질때까지 나눈뒤에 비교 하면 된다. 쉬움.
D
어떤 줄이 사라지는 시간은 왼쪽이 사라지는 시간 + 1, 오른쪽이 사라지는시간 + 1, 자기 높이 중 최소라는 사실은 알아냈으나 이후에 어떤식으로 접근해야 할지 방법이 떠오르지 않았다. DP로 풀면 된다고 하는데 아직 자세히 보지 않아서 모르겠다.
..editorial의 풀이는 와닿지가 않았는데 밑에 보니 dijkstra 풀이가 가능하다고 하더라. 각 블록들을 노드로 생각하고 가상의 소스노드에서 블록의 높이를 가중치로 가지는 간선을 연결한다. 인접한 블록들에 대해서는 가중치 1의 간선을 만들어 준다. 최종 답은 소스에서 다익스트라를 돌렸을때 최단거리가 가장 긴 노드까지 가는 거리가 된다.
E
모르겠다.
댓글
댓글 쓰기