_

1. Div2 A

사전순으로 가장 작게 만들거나 가장 크게 만들 때 가장 중요한 위치를 생각해보면 가장 앞에 있는 문자가 가장 중요한 것을 알 수 있다.
- 따라서 두 사람은 자신의 차례에 남아있는 index 중 최소 i를 잡아 $s_i$를 바꿀 것이다.
따라서 앞에서부터 두 사람이 번갈아 가면서 문자를 바꿔가며, 각 사람이 문자$s_i$를 바꾸는 규칙은 다음과 같다.
- Alice (최대한 사전순 최소 문자로 바꿈)
  - $s_i = a \Longrightarrow s_i = b$
  - $s_i \neq a \Longrightarrow s_i = a$
- Bob (최대한 사전순 최대 문자로 바꿈)
  - $s_i = z \Longrightarrow s_i = y$
  - $s_i \neq z \Longrightarrow s_i = z$

모든 monster를 죽이고 great hero도 죽을 수 있기 때문에, 마지막 great hero의 health value가 0 이상인지를 통해 판별이 불가능하다.
하지만, 마지막 공격 이전까지 great hero의 health value가 0보다 큰 경우 모든 monster를 죽일 수 있음을 알 수 있다.
즉, 마지막 공격을 i번 monster에게 한 경우 $$(i번\ 이외\ monster들의\ 공격) + (i번\ monster\ 공격\ 횟수-1) \times a_i < B$$인 경우 모든 monster를 죽일 수 있다.
이때 식을 변형하면 $$(모든\ monster들의\ 공격) - a_i < B$$가 되기 때문에 $a_i$가 최대가 되도록 $i$를 결정하여 i번째 monster를 가장 마지막으로 공격할 때 조건을 만족하는지 판별하면 된다.

Binary Search와 비슷한 방식을 사용하면 된다.
다음 조건들을 만족하는 (s, e) 구간을 계속 관리하자.
- $a_{s-1} > a_{s}$
- $a_{e} < a_{e+1}$
처음 (s, e) 구간을 (1, N)으로 초기화하면 조건을 만족하는 것을 알 수 있다.
(s, e) 구간의 크기를 계속 줄일 건데, 다음과 같은 연산을 할 수 있다.
- $s\leq m < m+1 \leq e$인 $m$을 잡자.
  - $a_{m} < a_{m+1}$인 경우 : 구간을 (s, m)으로 갱신
  - $a_{m} > a_{m+1}$인 경우 : 구간을 (m+1, e)로 갱신
- $m = (s+e)/2$로 $m$값을 설정하면 구간 크기는 항상 절반으로 줄어든다.
마지막에 구간이 (x, x+1)꼴로 남으면 답은 $a_x, a_{x+1}$ 중 작은 값의 index가 된다.
구간이 (x, x)꼴로 남으면 답은 x가 된다.

i번째 원소를 보고 있을 때 DP[j][k] = (x, y)와 같이 Pair를 사용하여 두 값을 저장한다.
- j : 0인 경우 $a_i$는 $a^{(0)}$에 위치 / 1인 경우 $a_i$는 $a^{(1)}$에 위치
- k : 0에 $seg(a^{(0)}) + seg(a^{(1)})$의 최댓값 저장, 1에 $seg(a^{(0)}) + seg(a^{(1)})$의 2번째 최댓값 저장
- x : 저장된 $seg(a^{(0)}) + seg(a^{(1)})$ 값
- y : 해당 $seg(a^{(0)}) + seg(a^{(1)})$를 갖는 경우에서 $a^{(1-j)}$에 위치한 마지막 원소의 위치
i번쨰 원소 $a_i$를 $a^{(0)}$ 또는 $a^{(1)}$에 추가할 때 마지막 값이 $a_i$인 경우와 $a_i$가 아닌 경우 2가지 경우에 $seg(a^{(0)}) + seg(a^{(1)})$값에 다른 변화가 생긴다.
따라서 DP 테이블에 k를 이용하여 최댓값을 갖는 2가지 케이스를 저장해주면서 테이블을 채우면 답을 구할 수 있다.