1월 23일, 24일 PS

원래 23~31일 해서 정리해서 올릴려고 했는데 25일부터 적는 걸 깜빡했다.

기억 안나서 이거라도 올린다

1 / 23

solved.ac에서 /olympiad *p -solved_by:$me 로 랜덤 돌림

 

USACO US Open 2015 Contest Gold : 팰린드롬 경로 3

가장 먼저 떠오르는 풀이는 $dp[i][j][k][l]$를 중간에서 시작해서 현재 $(i,j)$랑 $(k,l)$일 때 팰린드롬 경로 개수로 정의한 다음에 푸는 것이다. 하지만 메모리, 시간 모두 $O(N^4)$ 으로 불가능해 보인다. 

그런데 시간은 사실 가능하다. $(i,j)$에 있을 때 유효한 $(k,l)$ pair가 $O(N)$개 밖에 없다는 사실을 관찰할 수 있다.

이제 메모리를 $O(N^3)$으로 줄일 수 있다. $(i,j)$에 대해 유효한 $(k,l)$를 미리 벡터에 저장하는 등의 전처리를 통해 $dp[i][j][num]$ 등으로 처리할 수 있고, 이래도 메모리가 약 500MB로 제한인 256MB를 초과하기 때문에 실제로 계산하는 $(i,j)$는 모두 정사각형 대각선 윗쪽 부분이라는 점을 이용해 정확히 반으로 줄일 수 있고 250MB로 AC를 받을 수 있다.

정해는 $(i,j),$ $(k,l)$ 대신 $(j,l)$만 저장해도 $i$와 $k$를 얻을 수 있다는 점을 이용해 3차원 table을 정의하고 토글링하는 것으로 보인다.

여담으로 백준에 팰린드롬 경로 2가 없는 것 같다.

 

IOI 2010 Day 1 : Quality of Living

별 생각이 다 드는 문제인데 심플하게 prefix sum + 파라메트릭 서치를 적용하면 풀 수 있다.

답에 대한 결정 문제를 해결하자. $f(x)$ := 답이 $x$ 이하인가? 로 정의하고, $A_{i,j}⩽x$이면 $1$, 아니면 $0$으로 설정해서 2d prefix sum을 $O(HW)$ 시간에 채운다. 그럼 이제 문제는 모든 $R\ast C$ 크기를 돌면서 영역 내 합이 $\lceil \frac{R\ast C}{2}\rceil$ 이상인지를 prefix sum으로 확인해주면 된다.

 

1 / 24

PST 복습 겸 XOR Maximization(Trie)도 같이 복습함. 그리고 https://kenkoooo.com/...userPageTab=Recommendation 몇개

 

BOJ 13505 : 두 수 XOR

Binary Trie로 풀 수 있는 꽤 유명한 문제 중 하나이다. 간단하게만 설명하면 트라이에 이진수 형태로 상위 비트부터 싹 다 집어넣고 x랑 xor해서 최대가 되는 y를 찾을 때, 현재 보고 있는 비트의 최대한 반대쪽으로 내려가는 그리디를 통해 찾는다.

근데 이걸 Segment Tree를 이용해서도 구현할 수 있다. $[0,{10}^9]$에서 수 개수를 카운트하는 합 세그먼트 트리를 구축한 후에 세그먼트 트리에서 이분탐색하는 기법처럼 0인 구간, 1인 구간을 나눠서 최대한 현재 비트 반대쪽으로 가주도록 하면 O(최대 비트 개수)에 처리할 수 있다. 구간 크기가 10억이라 다이나믹 세그먼트 트리를 이용해야 한다.

구현할 때는 구간 크기를 $[0,2^{30}-1]$ 처럼 $2^k-1$ 꼴로 잡으면 정중앙을 기점으로 비트가 반전되서 구현이 편하다.

 

BOJ 13538 : XOR 쿼리

바로 위에서 설명한 세그먼트 트리에서의 XOR Maximization을 PST에 때려박으면 풀린다.

쿼리별 풀이 한 줄 요약

1번 : PST에서 1개 update

2번 : 위에서 설명한 xor 최대 세그먼트 트리

3번 : 수가 추가되는게 O(Q)번이라서 일일히 제거해줘도 상관없고, 퍼시스턴트 세그니까 O(1)에 루트 옮겨줘도 된다.

4번 : [1,x] 합

5번 : 이분탐색 세그먼트 트리

 

ABC190 E : Magical Ornament

젬들의 인접 관계를 그래프로 생각해보자. 그럼 이 문제는 C가 주어질 때 C의 원소들을 모두 방문하는 최소 경로 길이를 찾는 문제이다.
먼저 bfs로 주어진 k개의 수들 간 거리를 구해서 완전그래프를 만든다. 그럼 답은 이렇게 만들어진 완전그래프에서 TSP 비슷하게 bit dp를 통해 구해줄 수 있다.

 

ABC321 F : #(subset sum = K) with Add and Erase

$dp[i]$ := 어떻게 잘 골라서 합이 i인 경우의 수로 정의하고 수가 추가/삭제될 때마다 얘를 적절히 처리해주면 된다.  $x$가 추가될 때는 $dp[i]$ $+=$ $dp[i-x]$를 뒤에서부터, $x$가 삭제될 때는 $dp[i]$ $-=$ $dp[i-x]$를 앞에서부터 해주면 된다.

추가 때 뒤에서부터 해야되는 이유는, 앞에서부터 덮어씌우면 하나의 $x$를 2번 이상 사용하는 대참사가 일어나기 때문이다.

마찬가지로 삭제될 때 앞에서부터 해야하는 이유는 뒤에서부터 하면 쓰지도 않은 $x$를 없애버린다.

코드는 짧은데 은근 생각이 까다로운 문제 중 하나.

이 문제는 이전에 한번 업솔빙 했는데도 recommendation에 나온다. 근데 못 풀뻔 했다