Longest Path to WF 팀연습 기록
2021/09/24 NEERC 2010
I : 시작하자마자 읽고 좀 고민하니 풀이가 나왔다. 코딩큐를 기다리며 구현 구체화를 했고 바로 AC. N에서 BFS를 돌려 1부터 시작했을 때 갈 수 있는 경로를 찾을 수 있고, 사전순으로 빠른 경로가 나오도록 갈 수 있는 경로중 가장 $c$가 작은 경로만을 선택하게 다시 1부터 시작하는 BFS를 돌리면 된다.
평소와는 다르게 문제를 읽는 담당이 되었었다. 나는 풀이가 잘 나오지 않았었고, 기하 문제 및 비교적 쉬운 문제들을 두분이서 모두 해결하셨다.
J : 정말 열심히 구현했다. 다행히(?) BC의 풀이가 금방 나오지 않아 코딩큐가 비어있어서 여유롭게 코딩했다. 체감상 2시간은 잡은거 같다.
Upsolved
A : 열심히 구현하면 된다. 누적합을 이용한다면 더 쉽게 구현할 수 있다.
2021/09/24 NEERC 2009
D : I를 열심히 고민하고 있었는데, 풀이가 잘 나오지 않아 솔브가 나온 문제를 잡게 되었다. 간단한 map 기본문제
F : edenooo님이 I 풀이가 나와서 또다시 솔브가 나온 문제를 잡게 되었다. 단어의 길이가 짧으면 짧을수록 좋으니깐 한글자 단어부터 우선순위 큐에 넣고 하나씩 빼는데, 만약 그 단어가 단어장에 없으면 정답에 추가하고 아니라면 스킵한 뒤에 그 단어의 뒤에 26가지의 알파벳을 더한 문자열을 다시 우선순위 큐에 넣는다. 정답의 개수가 $N$개 미만 일때까지 반복하기 때문에 우선순위 큐에서 뽑히게 되는 단어의 개수는 최대 $N+M$개이고, 이 개수에 $26$을 곱한 만큼 우선순위 큐에 다시 들어가므로 충분히 시간내에 돈다.
G : 또또 솔브가 그나마 나온 문제를 잡게 되었다. $(n-1)(m-1)$번의 이동을 시뮬레이션 하면 각 $i$가 어디로 이동하는지, 그리고 $i$가 더해지는 횟수를 구할 수 있다. 이를 모든 $i$에 대해 저장하고 스파스 테이블을 $10^{100}$이 돌어갈 만큼 전처리해 놓는다면 각 $i$마다 로그에 답을 찾을 수 있게 된다. 코포에서는 256MB로 $ 10^{100} < 2^{334}$인 점을 이용해 아슬아슬하게 메모리 제한을 통과할 수 있었지만, 백준은 128MB라서 $10^{100} < 4^{167}$으로 메모리를 절반으로 줄인채로 맞았다.
Upsolved
2021/09/24 NAIPC 2019
J : NM DP 를 세운뒤 경우의 수를 잘 세워주면 된다. 풀이가 금방 나왔는데 머리가 꼬여서 한번 갈아엎었다.
M : 이것저것 왔다갔다 하다가 솔브수가 나와서 잡았다. 구간을 절반씩 나눠가면서 경우의 수를 잘 세주면 된다. 나눠지는 두 구간에 속한 원소가 완전히 다른지, 아니면 두 구간의 원소가 순서까지 정확히 같은지 판별해야 하는데 각각을 서로 다른 수열과 쿼리 2, 해싱을 이용해 풀어 뇌절했다. 그냥 머지소트를 하는대로 나이브하게 구현해도 상한이 $O(N \log N)$임이 보장되기 때문에 코드도 짧게 나온다. 하지만 다시 구현하는 건 귀찮으므로 패스.
저번과 마찬가지로 문제를 읽는 담당이 되었다. 어려운 문제를 Aeren님이 다 푸셔서 성적은 잘 나왔는데 나는 거의 한게 없었다.. E번 풀이를 도와준 정도?
Upsolved
E : $2^M$의 모든 경우에 마지막 두개 $i,j$를 선택했을 때 가능한 $k$를 찾으면 된다. $i,j,k$쌍을 비교하기 위해 전처리로 $O(N^2M)$, DP를 전이하는 데 $O(N^3)$으로 총 시간복잡도 $O(2^M(N^3+N^2M))$으로 빡빡하게 돌아간다. 코드를 보면서 디버깅을 도왔기 때문에 거의 그대로 코딩했다.
2021/09/24 NAIPC 2017
J : 연산의 결과를 본다면 결국 같은 수의 하얀 돌과 검은 돌을 지울 수 있다. 즉, 마지막에 한개씩의 돌을 남기긴 위해서 입력으로 같은 수의 돌이 들어와야 한다. 같은 수의 돌이 있다면 3개의 돌을 선택해서 같은 색의 두 돌을 뺄 수 있어서 항상 가능함을 볼 수 있다.
그 뒤에 약 4시간동안 D를 잡았지만 계속 풀이가 터진채로 못 풀었다. 업솔빙 예정..
Upsolved
D : 문제를 다르게 보면 트리 위에서 LIS를 구하는 것으로 볼 수 있고, 이는 리프 노드부터 multiset을 이용해 관리한다면 small-to-large를 이용해 제한시간 내에 풀 수 있다.
중간에 5번의 팀연습이 추가로 있었지만 초반 몇번을 너무 못풀어서 블로그 글을 쓸 의욕이 나지 않았다. 다시 시작..
2021/10/12 NEERC 2015
L : 그냥 브루트포스 문제
B : 
이런 형태로 열심히 construct 하면 된다.
Upsolved
D : 재귀적으로 문제를 해결하면 된다. $N$이 짝수라면 $N/2$를 해결한 뒤 나온 수의 목록에 $2$를 곱해주면 되고, 홀수라면 $N$보다 작은 $3^{M}$을 찾아서 목록에 추가하고 $N-3^M$을 해결하면 된다. 홀수 다음에는 반드시 짝수가 오게 되므로 나중에 나올 수에는 추가로 앞의 수보다 $2$가 한번 더 곱해지고, 당연히 수는 줄어들어서 $3^M$보다는 작은 $3$의 제곱수가 곱해지면서 조건에 맞는 수열이 만들어진다.
E : - 가 있으면 나오는 숫자 다음에 + 를 추가하면 된다. leading zero 나 수가 한자리 일때 등을 잘 처리해줘야 한다.
G : 보통 구현하는 위상정렬에서 큐 대신 우선순위 큐를 사용한다면 사전 순 최소를 뽑아낼 수 있다. 우선순위 큐에서 원소를 뽑아낼 때 K 가 남아있다면 선택을 미룰 수 있다는 뜻이므로 K를 감소시킨 뒤, 다른 우선순위 큐에 저장해놓는다. $N$개의 수를 뽑아내지 못했는데 우선순위 큐가 비어있다면, 다른 우선순위 큐에서 원소를 가져와서 진행시켜야 한다. 추가해야 하는 조건이 조금 더 있지만, 생략한다.
H : s[0] * 31 + s[1] == t[0] * 31 + t[1] 인 s, t를 찾은 뒤 두 문자열을 잘 배치해서 1000가지 종류를 만들면 된다.
J : $p_r$번 티켓으로 여행을 마칠 수 있다면 $p_{[r+1,n-1]}$티켓으로도 여행을 마칠 수 있다. 이분탐색으로 가장 작은 $r$을 찾고, $\min p_r..p_{n-1}$을 출력하면 된다. $r$이 가능한지 판별은 일차원 dp + 세그먼트 트리로 간단히 구할 수 있다.
K : 각도만 보기로 했을 때, i -> j, j -> i 가 가능한지 판별한 뒤 둘다 가능하다면 i->j가 가능한 것으로, 일차원 dp로 $O(N^2)$에 풀 수 있다.
대회중에 충분한 시간을 고민했었다고 생각한 D, K는 풀이를 까 봤는데, 정말 좋은 문제들이었다. 이런 좋은 문제의 풀이를 찾아내야 하는데… 대회 끝나고 보니 푼 문제가 없는거나 다름 없었다
