목록PS (25)
LoCeL
문제는 여기에서 확인 가능하다. permutation이 주어졌을때, 이것을 최소 몇 번 합성하면 identity permutation이 되는가를 묻는 문제로, disjoint cycle을 모두 찾아주고, 찾은 cycle들의 length의 최소공배수가 섞기 수열의 궤적이 된다. 예를 들어서 섞기 수열이 $(3\;2\;5\;6\;1\;4)$로 주어져있다고 하면, 원래의 수열 $(1\;2\;3\;4\;5\;6)$에서 1은 3과 5를 거쳐서 1로 돌아오고, 2는 항상 제자리에, 4는 6을 거쳐서 다시 제자리로 돌아오게 된다. 따라서 주어진 섞기 수열의 disjoint cycle은 $(3\;5\;1)$, $(2)$, $(6\;4)$임을 알 수 있고, 첫번째 cycle은 3번마다, 세번째 cycle은 2번마다 제자..
대회 후기 총 500점 만점에 140점으로.... 여태 프로그래밍 대회를 나가면 한문제도 제대로 못풀고 시간을 보냈지만 이번엔 그래도 한문제라도 제대로 풀어서 다행이라고 생각하고 있다. 7월 말 즈음에 본격적으로 공부를 시작해서 그래도 실력이 좀 늘었다고 생각했는데 정작 삼분탐색을 떠올리지 못해서 갈길이 한참 멀었구나 하는 생각이 들었다. NYPC가 참가상을 잘 챙겨준다는 얘기를 많이 들어서 기대했었는데 시상식 할때 홀에 들어가서 비닐봉투 종이봉투 한가득 선물이 들어있는 것을 보고 좀 감동하기도 했다. 도시락도 괜찮았고... 전체적으로 참가자들을 잘 챙겨주는 느낌이었다. 점심 진짜 맛없었던 어느 대회하고는 차이가 솔직히, 진짜 솔직하게 말하면 대회 시작 15분 쯤에 1번을 풀고나서 남은 시간동안 나머지 ..
IOI 2018 1일차 첫번째 문제입니다.문제는 여기에서 확인하실 수 있습니다. 우선 press를 $4N$번 호출하여 문자열을 찾는 것은 쉽고, 이를 $2N+1$로 줄이는 것도 어렵지는 않습니다.풀이를 시작하기에 앞서, $S[i]$는 구하고자 하는 문자열 $S$의 $i$번째 문자라 하겠습니다. 1. $S[1]$ 결정"AX", "AY"이 두 문자열에 대해 질의를 수행합니다.둘다 1 이상일 경우엔 A가 $S[1]$이 되고, 둘다 0일 경우엔 B가 $S[1]$이 되며, 둘중 하나가 1이면 X 또는 Y가 1로 결정됩니다. 2. $S[2]$ ~ $S[N-1]$ 결정한번의 질의를 수행하여 각 문자를 결정해야합니다.만약 첫번째 문자가 A인 경우, $i$번째 까지 구해둔 문자열을 $T$라고 했을때, 문자열 $T+$"B..
PS를 공부하기 시작한 후, 얼마 지나지 않아 치르게 된 대회이다. 열흘동안 20문제를 풀었는데 그 중에서 14문제를 풀고, 5문제에서 부분점수를 받아 3000점 만점에 2225점으로 아쉽지만 그래도 만족스러운 점수를 받을 수 있었다. 풀이부터 정리해보고자 한다. (코드는 귀찮으니까... 공유 안해야지) 1 - 아이템 구매 P, Q, W가 주어지면 정수 부정방정식$Px + Qy = W$를 만족하는 $(x, y)$를 아무거나 하나 찾으면 된다. 2 - 승리팀 찾기 2:10.11 이렇게 주어지면, $2 \times 60+10.11$이렇게 변환하면 일대일 대응이 되어서 float형으로 쉽게 저장할 수 있다. 이렇게 저장된 시간을 기준으로 정렬하고, 문제에서 주어진 조건에 맞게 점수계산을 하면 된다. 3 - 줄..
2018 UCPC에 나가지는 않았지만, 문제가 Backjoon Online Judge에 업로드 되어있어서 풀어보았습니다. 문제는 여기에서 확인할 수 있습니다. 문제가 길고 복잡해보여서 어렵게 느껴질수도 있지만, 생각보다 간단한 문제입니다. 게임의 어떤 시점에서, 게임판에 놓여져있는 말의 깊이의 합을 생각해보면, 말을 하나씩 옮길때마다 그 합이 1씩 줄어든다는 사실을 알 수 있습니다. 그리고 그 합이 0이 되면, 게임이 끝난다는 것을 알 수 있죠. 게임에서 최선을 다했을 때, 초기상태의 게임판에 놓여있는 말들의 깊이의 합 만큼 말이 이동하게됩니다. 그리고 성원이가 먼저 시작하였고, 성원이가 이기기 위해서는 성원이가 마지막으로 말을 옮겨야 하니, 초기 상태에서 깊이의 합이 홀수가 되면 성원이가 이길 수 있구..