I를 못풀어서 어쩌나 했는데 그거 빼고 다 풀어서 다행이다. 말린거 같았는데 생각보다 나쁘지 않았음
Short Diary (스포일러 주의)
A (0:34 +1)
(hyea) 처음과 끝 조건을 잘 보자, 실수를 쓰면 풀리는 문제지만 BigInteger를 쓰는게 안정적인것 같다
B (4:09)
(alex9801) Yet another ant problem. 개미에 색깔이 추가되었지만, 어렵지 않게 풀 수 있다.
(koosaga) 기본적으로 원에 올려놓은 개미 문제. 일반적인 개미 문제랑 관찰이 크게 다르지 않다. 사실 원이라서 엄청 헷갈렸는데 민규가 많이 도와줬다.
C (1:44)
(hyea) 적당한 관찰을 하면 풀 수 있는 문제이다. 숫자가 작아서 DB를 만들어도 된다.
D (2:47 +3)
(hyea) 수식을 단순화 시킬 수 있으면 단순화 시키자. Birthday paradox는 randomized된 풀이를 구하는데 도움이 된다.
E (3:16 +1)
(koosaga) joi spring camp 2014 허수아비랑 동일한 문제인데 너무 오래전 문제라 풀이를 다시 생각했다. (당시에는 되게 복잡하게 풀었던 거 같음)
x축으로 정렬하고 분할 정복을 하면 풀린다. 왼쪽 사이드를 L로 오른쪽 사이드를 R이라 두면, R에서 고를 수 있는 정점들이 단조적인 양상을 띔.
R에서 고를 수 있는 정점들을 스택에 저장하고, 적당히 이분탐색 하면 된다.
F (4:39 +5)
(alex9801) P=NP PPAP. 문제를 단순화하는 과정에서 놓친게 없는지 잘 확인하자.
(koosaga) 대회 끝나기 직전에 내가 풀이 반례를 찾았다. 그걸 고치니 AC가 나왔다. 그냥 그래서 기분이 좋았다...
G (2:15 +4)
(hyea) 내 컴퓨터에서는 1.97초 나왔는데
H (1:48 +1)
(koosaga) 첫번째 관찰은 shortest path의 시작점이 입력으로 주어진 점 중 하나라는 것. 이 중 아무 정점 v를 잡고 다익스트라를 하면, shortest path의 시작점 후보가 {v, v에서 가장 먼 입력에서 주어진 점} 딱 두개로 좁혀진다. 그래서 v를 시작으로 하며 모든 점을 포함하는 최단 경로를 찾으면 된다. 다익스트라로 하면 되는데 디테일이 많음
