나는 코더다 2017년 선발고사 대비 2차 모의고사 풀이

나는 코더다 2017년 선발고사 대비 2차 모의고사

많은 분들이 참가해주셨습니다. 감사합니다.

Acrobatics (원제 : CIRCUS / 출처 : Balkan OI 2015)

Circuit (원제 : Wires and Switches / 출처 : IOI '95)

다양한 풀이가 있을 수 있다. 여기서는 내 풀이를 소개하도록 하겠다.

각각의 연산에 대한 비용이 발생하기 때문에, 연산을 최소화해야한다는 생각이 들 것이다. 그러한 생각을 하다 보면, 여러 개의 스위치를 켠 상태에서, 여러 램프를 확인하는 작업이 꼭 필요하다는 결론이 나온다.

풀이 1

이쪽의 접근은 왠지 절반씩 하는 접근이 가능할 것 같다는 생각이 든다. 예를 들어, 전체의 스위치를 두 그룹으로 나눈다. 한 쪽 스위치를 모두 켜고, 모든 램프를 검사하면, 켜져 있는 램프들이 어떤 스위치들과 연결되어있는지를 알 수 있다. 그러면 나머지 램프들은 자연히 나머지 스위치와 연결되어있을 것이다. 그러고 보니, 문제가 똑같은 모양의 두 개의 문제로 쪼개져있는 것이다! 이것을 계속 반복해줄 수 있다는 생각이 들었다. 다음과 같다.

 
​x
typedef std::vector<int> V;
​
void work(V L, V S){
    if(L.empty() || S.empty()) return;
    if(S.size() == 1u){
        for(int l : L) answer(l, S[0]);
        return;
    }
    V Sa, Sb, La, Lb;
    int sz = S.size();
    for(int i=0; i<sz/2; ++i)  Sa.push_back(S[i]);
    for(int i=sz/2; i<sz; ++i) Sb.push_back(S[i]);
    for(int x : Sa) toggle_switch(x);
    for(int x : L) (test_lamp(x)?La:Lb).push_back(x);
    for(int x : Sa) toggle_switch(x);
    work(La, Sa);
    work(Lb, Sb);
}
​
void analyze_circuit(int N){
    V a, b;
    for(int i=1; i<=N; ++i) a.push_back(i), b.push_back(i);
    work(a, b);
}

그런데 이렇게만 하면 70점이 나온다. toggle_switch의 호출이 너무 많기 때문이다.

생각해보면, toggle_switch 함수를 호출해 줄 때는, 바로 이전의 work의 호출에서 몇 개의 스위치를 켜준 상태이다. 때문에 굳이 껐다 켤 필요가 없고, 스위치의 상태가 내가 원하는 상태가 아닐 때만 호출해주면 된다. 따라서 이렇게 해줄 수가 있다.

 
xxxxxxxxxx
bool on[91];
​
void work(V L, V S){
    if(L.empty() || S.empty()) return;
    if(S.size() == 1u){
        for(int l : L) answer(l, S[0]);
        return;
    }
    V Sa, Sb;
    int sz = S.size();
    for(int i=0; i<sz/2; ++i)  Sa.push_back(S[i]);
    for(int i=sz/2; i<sz; ++i) Sb.push_back(S[i]);
    for(int x : Sa) if(!on[x]) toggle_switch(x), on[x]=1;
    for(int x : Sb) if(on[x]) toggle_switch(x), on[x]=0;
    V La, Lb;
    for(int x : L) (test_lamp(x)?La:Lb).push_back(x);
    work(La, Sa);
    work(Lb, Sb);
}
​
void analyze_circuit(int N){
    V a, b;
    for(int i=1; i<=N; ++i) a.push_back(i), b.push_back(i);
    work(a, b);
}

이러면 100점이 나온다.

풀이 2

스위치를 계속 절반으로 나눠가는 원리는, 그림을 그리며 잘 생각해보면 이런 방법과 거의 같다.

• 스위치의 번호를 2진법으로 나타냈을 때, 1의 자리가 1인 스위치들만을 켜고 나머지는 끈 상태에서, 모든 램프를 확인해본다. 만약 어떤 램프가 켜져있다면, 그 램프의 스위치의 번호는 1의 자리가 1일 것이다.
• 2의 자리가 1인 것을 똑같이 확인.
• 4의 자리가 1인 것을 똑같이 확인.
• 8의 자리가 1인 것을 똑같이 확인.
• …

소스는 다음과 같다. 위의 풀이와 방법은 유사하나 소스가 훨씬 짧다. 여기서도 최적화를 위해, i번째 비트와 i-1번째 비트의 상태가 다른 스위치들만 뒤집어준다. 그러면 모든 i마다 뒤집어주는 스위치의 갯수는 약 N/2이다. 따라서 1.5NlgN번의 호출을 수행하게 되고, $$1.5 \cdot 90 \cdot 7 = 945 \leq 1000$$ 이므로 만점을 받을 수 있다.

 
xxxxxxxxxx
int ans[91];
​
void analyze_circuit(int N){
    for(int i=0; i<7; ++i){
        for(int j=1; j<=N; ++j) if(bool(j&(1<<i)) != bool(j&(1<<(i-1)))) toggle_switch(j);
        for(int j=1; j<=N; ++j) ans[j] += (1<<i)*test_lamp(j);
    }
    for(int i=1; i<=N; ++i) answer(i, ans[i]);
}

Signal (원제 : Relay / 출처 : Croatian OI 2016)

Wakeup (원제 : Solar lamps / 출처 : Polish OI 2013/2014 Stage 3)

원래의 문제에서는 램프가 비추는 방향이 각도의 형태로 주어졌다. 모든 램프가 같은 각도를 비추긴 하지만, 이것을 잘 판단하여 좌표압축을 시켜야 하는 번거로움이 있기에, 대회를 준비하면서는 그러한 부분을 빼버렸다. 덕분에 원래 대회의 데이터를 ①각도를 고려하여 좌표압축한 후 ②랜덤한 좌표로 다시 할당하여 ③새로운 출력 형식으로 출력하는 과정을 거쳐야 했다. 이 과정에서 실수하지 않을까 걱정했는데, 푼 사람들이 나왔기 때문에 다행히도 그러한 실수는 없었던 것 같다.

풀이 1

어떤 위성이 켜지는 데에는 자신보다 x 및 y가 작거나 같은 위성들만 영향을 끼친다. 따라서 어떤 위성보다 x좌표가 작거나 y좌표가 작은 위성들이 켜지는 시간을 모두 알았다면 우리는 그 위성이 켜지는 시간을 잘 구할 수 있을 것 같다는 생각이 든다. 즉 x좌표, 같다면 y좌표가 증가하는 순서대로 정렬한 후, 하나하나 보며 답을 계산하면 될 것 같다.

그렇다면 어떤 위성에 대해서, 지금까지 처리한 위성들 중 y좌표가 자신보다 작은 것들에 대해서, 켜져 있는 것의 갯수가 $$k_i$$ 가 되는 순간을 찾으면 될 것이다. 이를 위해 2D segment tree를 구성할 수 있다.

$$(y_{i}, ans[i])$$ 의 점들을 찍고, $$0 \leq x \leq y_{i}, \; L \leq y \leq R$$ 에 해당하는 직사각형에 대한 query를 $$L, R$$ 의 범위를 줄여가며 수행하면 될 것이다. 각각의 쿼리를 수행하는 데에 드는 시간을 생각해보자. 직사각형 query를 통해 $$i$$ 번째 위성에 대한 처리를 이분탐색으로 수행하면, 직사각형 query가 $$O(lg^{2} N)$$ 의 시간이 걸리므로, 총 $$O(lg^{3} N)$$ 의 시간이 걸린다. 그러나 이것을 루트에서 내려가는 식으로 잘 구현하면, 이분탐색이 필요하지 않고, 총 $$O(lg^{2} N)$$ 의 시간이 걸리게 된다.

풀이 2

어떤 점의 답이 $$t$$ 이하라면, 그 점의 번호가 $$t$$ 이하이거나, 자신을 비출 수 있는 점 중에 답이 $$t$$ 이하인 점들의 갯수가 $$k_{i}$$ 개 이상이어야 할 것이다. 그러면 $$x$$ 좌표가 증가하는 순서대로 점들을 보면서, $$y$$ 좌표 축에 대한 BIT를 만들어서 값을 업데이트해줄 수 있다. 즉 점 $$i$$ 를 확인할 때에는 $$sum(y_{i})$$ 만을 확인해주고, 그에 대한 계산이 끝나면 만약 그 점의 답이 t 이하라면 $$upd(y_{i}, 1)$$ 을 해주는 것이다. 따라서 $$O(NlgN)$$ 의 시간에 답을 기준으로 점들을 분류할 수 있다. 이제 답이 $$t$$ 이하인 점들은 또다시 적절한 $$t_{new}$$ 를 잡아 재귀적으로 처리할 수 있을 것 같다는 생각이 든다. 그런데 답이 $$t$$ 초과인 점은? 답이 $$t$$ 초과라면, $$t$$ 이하인 점들이 어떤 것들이 있는지는 사실 별 상관이 없다. $$t$$ 초 이후의 시간을 볼 때는, 자신보다 $$x, y$$ 좌표가 작거나 같은 점들의 갯수만큼은 항상 보장된 것이다. 즉, $$sum(y_{i})$$ 만큼을 $$k_{i}$$ 에서 빼줄 수가 있다라는 것이다.

그렇다면 답에 대한 분할 정복을 생각해볼 수 있다.

bit = new BIT

work(ans_l, ans_r, points):
    if ans_l > ans_r: return
    if ans_l == ans_r:
        mark answer of points
        return
    pick some T from [ans_l, ans_r]
    p1 = []
    p2 = []
    for p in points:
        s = bit.sum(p.y)
        if (s >= p.k) or (p.index <= T):
            append p into p1
            bit.upd(p.y, +1)
        else:
            p.k -= s
            append p into p2

    for p in p1: bit.upd(p.y, -1)

    work(ans_l, T, p1)
    work(T+1, ans_r, p2)

적절한 T의 선정이 중요해보이는데, 직관적으로도 (ans_l + ans_r)/2가 적절해보인다. 그러한 T를 선정하면, 총 $$O(Nlg^{2}N)$$ 의 시간이 걸린다는 것을 증명할 수 있을 것이다.