Random Problem Solving 1

Intro

정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다.

20045 Trading System

먼저 다음과 같은 값을 찾는다.

• 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$

이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다.

이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다. 이를 위해서는 구간합이 $x$를 초과하는 구간의 개수가 $k$개 이상 있는지를 빠르게 찾아낼 수 있어야 한다. 구간합 배열을 $S$라고 하자. $[i,j]$의 합은 $S[i] -S[j-1]$로 나타낼 수 있으므로, 결국 $S[0] = 0$이라고 둔다면 각 $S[i]$에 대해 $0 \le j<i$이면서 $S[i] - S[j] \ge x$인 $S[j]$의 수를 모두 구해서 더한 것이 $k$ 이상인지를 찾으면 된다. Naive하게 구현한다면, 원소들을 좌표압축 후 세그먼트 트리를 준비해 두고 $i$가 증가할 때마다 $S[i]$를 세그먼트 트리에 업데이트 하면서 $S[i]-x \ge S[j]$인 $S[j]$의 개수를 구해주면 된다. 이는 각 업데이트에 $O(\lg n)$, 각 쿼리마다 $O(\lg n)$, 총 반복이 $O(n)$번이므로 $O(n(\lg n + \lg n))$$=O(n \lg n)$ 이 된다. 파라메트릭에서 수의 범위 $p$에 대해 $O(\lg p)$가 붙는다는 것을 고려해 볼때 1초면 힘들다는 것을 알 수 있다.

업데이트와 쿼리에서 시간을 줄여 보자. 우선 같은 세그먼트 트리를 굉장히 여러 번 사용하는 것을 알 수 있으므로, PST를 사용하면 업데이트를 처음 한번만 해 주면 된다. 고로 $\lg p$가 하나 날아가 전체 복잡도가 $O(n \lg n)$으로 줄어든다. 쿼리에서도 야매 테크닉을 사용할 수 있다. $k$가 생각보다 작다는 점에 착안해보자. $S[i] - S[j]$, 즉 부분합 중에서 $S[i]-x \ge S[j]$의 조건이 만족하는 구간이 하나 이상 존재하는지는 각 $i$에 대해 가능한 $S[j]$의 최솟값을 기록해둠으로서 전처리 $O(n)$ 이후 $S[i] - x \ge \min$임을 체크하여 질의당 $O(1)$에 확인할 수 있다. 만약 이 체크를 통과하지 못한다면, 가능한 구간의 개수는 증가하지 않을 것이다. Naive 풀이에서 우리는 가능한 구간의 개수가 $k$개 이상인지를 체크하는 결정 문제를 해결하는 중임을 기억하자. 만약 $i$에 대해서 구간을 하나라도 찾는 것이 불가능한 경우에 그냥 패스해버리면, 세그먼트 트리에 쿼리를 날리는 횟수는 한 번 쿼리를 날릴 때마다 적어도 횟수가 1회 증가하므로 결정 문제 당 $k$번 이하가 된다.

이 두 가지 테크닉을 동시에 적용하면 복잡도는 $O(n \lg n + n \lg n \lg p)$로, 추하지만 굉장히 안정적인 복잡도가 나온다. Priority Queue를 쓰는 풀이도 있다고는 하는데 그러한 우아한 풀이는 염증이 나기에 작성하지 않겠다.

18944 Non-Decreasing Subarray Game

자명하게 Yuto가 구간 내에서 어떤 숫자를 부르면, Platina는 구간의 양쪽 끝 중 자신에게 더 유리한 쪽을 고를 것이다. 따라서 구간 $[i,j]$가 주어졌을 때 우리는 Yuto가 $max(f([i,k]),f([k,j]))$를 최소로 하는 $i \le k \le j$를 고를 것이라는 것을 알 수 있다. $f(a,b)$는 $[a,b]$에서 얻게 되는 점수이다.

구간이 확장되면 반드시 점수는 순증가하기에, $k$가 증가함에 따라 $f([i,k])$는 순증가하고 $f([k,j])$는 순감소한다. 따라서 이 두 함수의 최대를 취하면 이 함수는 유니모달하고, 삼분탐색을 사용할 수 있다. (이해가 안 간다면 그림을 그려보자)

어떤 구간에 대해서 점수를 구하는 것은, 연속된 non-decreasing한 수들을 하나로 뭉쳐 두고 그 위에서 적절한 prefix sum을 사용하는 것으로 처리할 수 있다(이 부분이 문제 난이도의 99%를 차지한다). 직접 구현하고 분노해 보자.

17515 Maximizer

$N$이 짝수라면 $1$부터 $N/2$를 각각 $N/2+1$부터 $N$까지와 매칭시키면 된다.

$N$이 홀수일 때는 까다롭다. 적절히 백트래킹을 돌려 규칙을 확인해 보면 $N/2+1$와 매칭되는 수는 자유롭고 그 외에는 짝수와 같은 방식으로 매칭되어야 한다는 것을 확인할 수 있다. 따라서 $N/2+1$을 작은 그룹으로 취급할 것인지, 큰 그룹으로 취급할 것인지 두 경우를 고려해본 다음 그 중 더 나은 해를 출력하면 된다.

15825 System Call

다음과 같은 사실을 안다.

• $S$와 $\displaystyle 1 \le x \le S$ 에 대해 $\displaystyle [\frac{S}{x}]$ 로 가능한 수는 최대 $O(\sqrt S)$개이다.

버퍼 크기를 1로 설정해 놓고, 점점 키워나가면서 read 함수를 호출하는 횟수를 계속해서 갱신해 주자. 각 파일에 대해서 read 함수를 호출해야 하는 횟수가 변화하는 횟수는 위 lemma에 의해 $O(\sqrt {F_i})$번이다. 이 위치를 미리 모두 계산하여 저장해둔 후, 스위핑하듯이 버퍼 크기를 증가시키면서 함수 호출 횟수가 변화하면 갱신해주면 된다. 각 버퍼 크기에서 걸리는 시간은 독립된 두 변수인 함수 호출 횟수와 함수 호출 횟수에 걸리는 시간의 곱이므로, 이는 빠르게 계산해줄 수 있다. 시간복잡도는 $O(n \sqrt n)$이다.

13482 Java2016

문제가 길지만 실제로 사용해야 하는 정보는 별로 없다.

1을 확정적으로 만들 수 있다면, 임의의 수를 만드는 것은 그리 어렵지 않다. 1을 만들 확률을 $p$라고 하자. 그렇다면 매크로 8개를 정의해서 각각 $2^i$를 저장하고 있도록 할 수 있다. 이는 $2^i = 2^{i-1} + 2^{i-1}$로 할 수 있고, 모든 매크로가 옳은 정답을 내는 것은 대략 $O(p^{256})$정도의 성공 확률을 가진다. 따라서 충분히 높은 $p$를 가지면서 1을 만드는 매크로를 찾을 수 있다면, $c$를 이진수로 나타낸 뒤 각 매크로를 적절히 더해줌으로서 문제를 해결할 수 있다.

1을 만드는 매크로를 찾는 법은 다음과 같다. 재귀적인 매크로를 $k$개 정의해서, $a_1 = ? \space \max \space ?$이고 $a_k = a_{k-1} \max a_{k-1}$이라고 하자. 그렇다면 $k$에 대해서 매크로 $a_k$는 $2^k$개의 난수 중 최대값을 반환하는 매크로가 된다. 이 때 매크로가 255를 반환할 확률은 $\displaystyle 1-(\frac{255}{256})^{\exp(2,k)}$가 된다. $k=14$ 정도로 잡으면 이 값은 어림 잡아도 소수점 아래 10자리가 모두 9로, 사실상 1에 가까운 수가 되어버린다. 이 확률을 $t$라고 하자.

따라서 그 매크로를 $x$라고 할 때 $ y = x / x$인 매크로 $y$는 $p = t^2$의 확률로 1을 반환하게 된다. 이 경우에 $p^{256}$을 계산해 보아도 사실상 1에 매우 가까운 확률이 나오기에, 모든 테스트 케이스에 대해 정답을 출력할 여지가 충분하다. 여유롭게 AC를 받자.

13474 Boys and Girls

난 너무 어려웠는데 나 빼고 다 쉬웠대서 슬프다.

i) $N<15$인 경우

작은 경우의 데이터를 처리하기엔 귀찮으니 백트래킹으로 쳐내자.

이제 $d$를 정의하자. $d$를 왼쪽과 오른쪽에 있는 사람의 성별이 다른 사람의 수로 정의하면 문제를 다음과 같이 찢을 수 있다. 참고: $d$는 $n-x-y$로 구할 수 있다. 그 이유에 대해 간략하게 설명하자면, 결국 $d$에 속하는 사람은 $x$와 $y$를 하나씩 증가시키고 그렇지 않은 사람은 둘 중 하나만 증가시키기 때문이다.

ii) $d$가 홀수거나 음수

존재할 수 없다. 구간을 잘 묶어 보면 항상 조건을 만족하는 사람은 쌍을 이뤄서 나타난다는 것을 확인할 수 있다.

iii) $d=0$

GBGBGBGB...가 반복되는 짝수 길이 수열과 BBBB... 또는 GGGG... 밖에 존재하지 않는다.

iv) $d=2$

iii과 비슷하게 구간을 적절히 분리해서 처리해줄 수 있다.

v) $d=4k$

BGBG를 $k$번 반복한 문자열에 G를 $y-d$개, B를 $x-d$개 붙이면 된다. 이 경우에 construction은 반례가 없다.

vi) $d=4k+2$

BBG에 BGBG를 $k$번 붙이자. 이 때 발생하는 $d$는 $4k$개이므로, G를 $y-d$개 그리고 B를 $x-d-1$개 붙이면 된다. 이 경우의 construction은 반례가 있는데, 당연히 이 붙여야 하는 개수가 음수가 되면 불가능하다. 주의해야 할 점은, $x-d$가 0이라 BBG에 BGBG를 붙여서 안 되면 GGB에 GBGB를 붙이는 방식으로 $x$와 $y$를 갈아끼울 수 있다. 두 경우 모두를 고려하고, 되는 경우가 없을 때 불가능함을 표시하면 된다.