(5/1 16:53 초판)(5/4 LM 풀이 추가, RST 약간 수정)(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가) 범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다. 팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다. 사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다. 후기는 그냥 좀 재미있던 것만 간략..
1. Fenced In (Platinum)독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번..
1. Digit DivisionSi = 주어진 숫자의 i자리 prefix를 mod M으로 나눈 나머지라고 하자. Si 배열은 선형 시간에 쉽게 계산할 수 있다.주어진 숫자들을 적당히 나눈 partition이 대충 [i1 + 1, i2] / [i2 + 1, i3] / [i3 + 1, i4] / ... / [i_{k-1} + 1, i_k] 와 같이 생겼다고 하자. 물론 i1 = 0, i_k = N이다. 이 partition이 올바르려면, 모든 1 이상 k 미만의 idx에 대해서 S_{i_{idx + 1}} = S_{i_ idx} * 10 ^ (i_{idx + 1} - i_idx) (mod M)을 만족해야 한다. 이 때, S_{i1} = 0 (mod M)임을 알 수 있다. 고로 S_{i2} = 0 (mod ..
- Total
- Today
- Yesterday