FunctionCup 2019

곧 있을 2023 함수컵을 대비해 2019 함수컵을 풀어 보았다. 굿바이 한별(79brue, flappybird, lisifu) 팀 연습 세션으로 5시간 동안 돌아 1068/1200점, 대회 중 2등의 성적을 기록했다.

 

나는 저 중 1-1, 1-2, 1-3, 2-1, 4-1을 맡았다. 1-x 문제들은 매우 쉬운 문제들이었기 때문에 사실상 2-1 푼 게 유일한 기여라고 할 수 있겠다. 4-1도 원래 무조건 풀었어야 했을 문제인데, 못 푼 게 아쉽다. 나머지 문제들 중에서는 어려운 게 많았는데 팀원들이 대부분 너무 잘 풀어줘서 고마웠다.

 

A. HicCup (0:13)

$X$에 대한 이분 탐색을 한다. 간단한 스택 문제이다. 스택을 통해 현재 상태를 오토마타 느낌으로 저장한다. 현재 상태는 H, HC, HC!!..!! 중 하나가 될 수 있다. 이런 상태를 스택에 쌓아 둔다. (괄호 문자열 찾기랑 비슷하다) 느낌표를 어떤 순서로 배치하는지가 중요한데, 그리디하게 하면 된다. 최대한 짧게 만들되, 방법이 없는 경우에만 $X$ 초과의 길이로 붙인다. $X=0$일 수 있다는 것에 주의해야 한다.

#include "hiccup.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int n;
char str[1000002];
 
bool able(int x){
    vector<int> stk;
    bool last = 0; /// 마지막이 느낌표
    for(int i=1; i<=n; i++){
        if(str[i] == 'H') stk.push_back(-1), last = 0;
        else if(str[i] == 'C'){
            if(stk.empty() || stk.back() != -1) return false;
            stk.back()++;
            if(x==0){
                last = 1;
                stk.pop_back();
            }
            else last = 0;
        }
        else{
            if(stk.empty() || stk.back() == -1){
                if(last) {}
                else return false;
            }
            else{
                stk.back()++;
                if(stk.back() >= x) stk.pop_back(), last = 1;
                else last = 0;
            }
        }
    }
    return stk.empty();
}
 
int HicCup(string S){
	n = S.size();
	for(int i=1; i<=n; i++) str[i] = S[i-1];
	int L = 0, R = n, ANS = -1;
	while(L<=R){
        int M = (L+R)/2;
        if(able(M)) ANS = M, L = M+1;
        else R = M-1;
	}
	return ANS;
}

B. King of Chairs (0:25)

당연히 $X=0$이고, 비트 전달 없이도 풀 수 있다. 그리디하게 생각하면, 어떤 궁녀의 무게가 $W_i$일 때 해당 궁녀가 앉을 수 있는 의자 중 가장 무게 한계가 낮은 의자를 배정하면 된다. 이런 의자가 없으면 서 있게 하면 된다.

 

#include "king.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll SendInfo(vector<int> W, vector<int> C) {
	return 0;
}

#include "vassal.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
set<pair<int, int> > st;
 
void Init(long long B, vector<int> C){
	int n = C.size();
	for(int i=0; i<n; i++) st.insert(make_pair(C[i], i));
}
 
int Maid(int W){
	auto it = st.lower_bound(make_pair(W, -1));
	if(it == st.end()) return -1;
	int ret = it->second;
	st.erase(it);
	return ret;
}

C. List of Unique Integers (0:32)

크기 $N$의 배열 $A$에서, 어떤 쿼리를 유용하게 쓸 수 있을까? 대충 $2N$ 번 정도 쿼리를 써야 하니 선형적인 접근을 생각해 보는 게 좋다. $[L, R]$과 $[L, R+1]$ 쿼리의 값을 비교했을 때 1 커진다면, $A_{R+1}$은 $[L, R]$ 구간에 없다는 것을 알 수 있다. 여기서 $L=1$로 고정하면, 각 수에 대해 처음으로 등장하는 위치를 $N$번의 쿼리로 알 수 있다. 이걸 반대로 돌리면 각 수에 대해 마지막으로 등장하는 위치를 알 수 있다. 수가 단 하나뿐인 경우 처음으로 등장하는 위치가 곧 마지막으로 등장하는 위치이므로, 이 칸들만이 유일하게 등장하는 수의 칸이다.

 

#include "unique.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
vector<int> PickUnique(int n){
    vector<int> ret(n, 1);
    vector<int> a(n), b(n);
	for(int i=0; i<n; i++){
        a[i] = UniqueCount(0, i);
        if(i && a[i] != a[i-1] + 1) ret[i] = 0;
	}
	for(int i=n-1; i>=0; i--){
        b[i] = UniqueCount(i, n-1);
        if(i<n-1 && b[i] != b[i+1] + 1) ret[i] = 0;
	}
	return ret;
}

D. On the Grid (2:20)

일단 문제 형태가 많이 복잡하니 수정해 보자. $N$명의 학생이 있고, $i$번 학생이 가진 막대기 길이를 $A_i$, $i$번 학생이 몇 번째에 넣는지 그 순서를 $B_i$라고 하자. $A$는 우리가 알아내야 하는 값이고 $B$는 우리가 정할 수 있는 값이다. 이때 쿼리를 날리면 반환되는 값은 $\max_{A_i + (n - B_i)}$임을 알 수 있다. $B_i = n - 1 - B_i$로 재정의하면 대충 $\max(A_i + B_i)$이 나온다고 생각해도 좋다. (뒤에 상수가 있지만 배제 가능하기 때문에...)

 

이제 $B_i$를 대충 아무 수열로 잡고 쿼리를 날린다. 이때 쿼리에 대한 답 $V$가 $n+1$이라면, $A_i + B_i = n+1$이 모든 $i$에 대해 성립하므로 $A_i$를 알 수 있다. 하지만 $n+1$보다 큰 경우에는 바로 알아낼 수 없다. 이때 $B_i \ge V - n$인 $i$들 중 하나에서 이 최댓값이 나왔다는 것을 알 수 있다. 나머지 칸들은 $A_i$가 아무리 커도 $n$이기 때문에 최댓값이 떴을 가능성이 없다. 위 조건을 만족하는 칸들을 후보 칸이라 하자.

 

후보 칸들의 $B_i$를 정렬한 이후, 전 순서에 있는 것들로 한 칸씩 바꿔 준다. 이때 기존에 $B_i$가 최소였던 것 하나만 최대로 바뀔 것이다. 이 하나의 값만 $B_i$가 증가하고 나머지는 감소한다. 이후 다시 쿼리를 날려 $V'$를 얻는다. 웬만한 경우 $V' < V$일 것이다. 그러나 만약 $V' \ge V$인 경우 여기서 최댓값이 될 수 있는 것은 방금 바꿔서 최대가 된 $B_i$ 위치뿐이라는 것을 알 수 있다. 이 칸을 확정짓고, $A_i$를 알아낸 뒤 $B_i = n + 1 - A_i$로 교체해 준다. (원래 이 값을 $B_j$로 갖고 있던 $j$가 있을 텐데, $B$값을 서로 교체한다고 생각하면 된다.) 그리고 위 과정을 반복하는 것이 기본적인 아이디어이다.

 

이 풀이가 성립하는 이유는 매 턴 쿼리를 날릴 때 1) 한 칸의 값을 알아내거나 2) $V$가 1 이상 감소하기 때문이다. 이 과정은 최대 $2N$번밖에 일어날 수 없다. 단 만점을 받으려면 생각보다 까다롭다. $A$값을 하나 알아낸 뒤의 처리에서 $V$가 확 증가하지 않도록 하는 처리도 필요하고, 그것을 위해서는 $V$로 알아낸 값에 해당하는 교체 후 다시 쿼리를 날려 이전의 $V$와 다음의 $V''$를 비교하는 식으로 해야 한다. 설명하기 꽤 복잡하니 자세한 건 코드를 보자.

 

#include "grid.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int n;
vector<int> ans;
bool usedIndex[1002], usedValue[1002];
 
int query(vector<int> vec){
    /// 실제: max(Ai + n - 1 - Bi), 이상: max(Ai + Bi)
    /// 따라서 수정이 필요
 
    vector<int> toQuery(n);
    for(int i=0; i<n; i++) toQuery[n-vec[i]] = i;
    return PutDisks(toQuery) + 1;
}
 
vector<int> SortDisks(int N){
    n = N;
    ans.resize(n);
 
    vector<int> vec(n);
    for(int i=0; i<n; i++) vec[i] = i+1;
 
    int val = -1, lastval = -1, exceed = -1; /// 바꾸고 난 뒤 val, 바꾸기 전 val, 넘었을 때 넘은 위치
    while(true){
        lastval = val, val = query(vec);
 
        if(val == n+1){ /// 모든 게 완벽하게 짝지어짐
            for(int i=0; i<n; i++) if(!usedIndex[i]){
                int ai = val - vec[i];
                ans[i] = ai;
            }
            break;
        }
 
        int criteria = val - n; /// rotate에 들어가는 기준
        int findingCnt = 0;
 
        for(int i=0; i<n; i++) if(!usedIndex[i] && vec[i] >= criteria) findingCnt++;
 
        if(findingCnt == 1 || (lastval != -1 && val > lastval-1)){ /// 남은 게 하나 or 1 감소하지 않아 exceed 처리
            int idx = 0;
            if(findingCnt == 1) while(usedIndex[idx] || vec[idx] < criteria) idx++;
            else idx = exceed;
            int ai = val - vec[idx];
            int bi = n + 1 - ai;
            int changedPosition = find(vec.begin(), vec.end(), bi) - vec.begin();
            swap(vec[idx], vec[changedPosition]), ans[idx] = ai, usedIndex[idx] = usedValue[bi] = 1;
            exceed = changedPosition;
            val = lastval;
            continue;
        }
 
        /// 이제 남은 게 여러 개고 1 감소한 상황
 
        vector<pair<int, int> > pairVec;
        for(int i=0; i<n; i++) if(!usedIndex[i] && vec[i] >= criteria){
            pairVec.push_back(make_pair(vec[i], i));
        }
        sort(pairVec.begin(), pairVec.end());
 
        /// 한 칸씩 오른쪽으로 민다
        for(int i=0; i<(int)pairVec.size()-1; i++){
            vec[pairVec[i+1].second] = pairVec[i].first;
        }
        vec[exceed = pairVec[0].second] = pairVec.back().first;
    }
 
	return ans;
}

 

J. 최적의 팀 구성 (19점) 

기본적으로 식을 보면 $X(A_i + D_j) + Y(P_i + P_j)$가 최대가 되는 $i$, $j$를 찾으면 된다. $i$가 정해지면 $j$는 $X \cdot _j + Y \cdot P_j$가 최대가 되는 것으로 자동 결정된다. 만약 이떄 $i$와 $j$가 같아지는 경우는 두 번째로 큰 $j$로 자동결정된다. 따라서 $XD_j + YP_j$가 최대인 두 개의 $j$값만 알면 충분하다. 비슷한 논리로 $i$도 이런 두 개만 알면 충분하다. 방법은 똑같으니 $i$를 알아내는 방법만 보자.

 

$f_i (\gamma) = A_i + \gamma P_i$를 직선에 그리고 보면 Convex Hull Trick 비슷한 느낌을 받을 수 있다. 실제로 컨벡스 헐 트릭의 그것을 쓰면 가장 큰 것의 $i$는 $O(\log N)$에 구할 수 있다. 두 번째로 큰 것을 구하는 과정이 어려운데, 시험 중에는 DnC로 해결하려고 했다. 대충 세그먼트 트리 구조로 Convex Hull 자료구조를 담고 $[1, i-1]$ 구간과 $[i+1, N]$ 구간에서 쿼리를 날려 구하려고 했는데, 로그제곱에 상수도 엄청 커서 TLE가 났고 결국 끝까지 해결하지 못했다.

 

로그를 하나 떼는 방법이 있는데 바로 Convex Hull Trick 자료구조의 역사를 활용하는 것이다. 일단 $[1, i-1]$ 구간에서 구하는 방법만 알아도 충분하다. (반대쪽은 그냥 똑같이 하면 된다) 이 트릭에서 직선은 스택 형태로 추가되거나 삭제되기만 하므로 (CHT를 할 때는 당연히 기울기 순으로 정렬해 두어야 한다) 이 과정을 트리로 모델링할 수 있다. 이제 트리에서 어떤 정점과 루트 사이의 경로에서 start_x를 두고 이분 탐색을 하는 느낌으로 노드를 찾으면 쿼리당 $O(\log N)$에 해결 가능하다.

 

에디토리얼은 더 쉬운 풀이를 쓰는 것 같다. 나는 이해를 못했다.