카카오 Code Festival 본선 1~6번 풀이

9월 9일 진행된 카카오 코드페스티벌 본선 8문제 중 앞 6문제에 대한 풀이다. 

나중에 좀 더 다듬어서 예쁘게 쓰고 싶었는데 그런 마음 가졌다가 안쓴 글이 한두가지가 아니라서 일단 되는대로 쓴다.

생각나는대로 짠거라 코드가 길거나 더럽다 ㅜ...

어차피 곧 카카오 테크 블로그( tech.kakao.com )에 풀이 글이 올라온다고 하니 제대로 된 문제 설명과 풀이는 그쪽을 기다리면 될 듯!

예선 설명도 테크 블로그에 있다 : tech.kakao.com/2017/08/11/code-festival-round-1/

1번. 단체사진 찍기

문제 : 카카오 프렌즈 8명(마리?)이 한줄로 서서 단체 사진을 찍으려고 한다. 그런데 프렌즈간 미묘한 관계가 있어서 각자 다른 프렌즈과의 거리에 대해 요구사항이 있다. 이 때 요구사항을 만족하는 줄서기 방법이 몇가지인지 구하라. 각각의 프렌즈는 A, C, F, J, M, N, R, T의 대문자로 나타내며, 요구사항은 "A~B=3"의 꼴로 나타낸다. 이 문자열은 A라는 프렌즈와 B라는 프렌즈 사이에 있는 프렌즈가 정확히 3명이 되어야 한다는 것을 의미한다. 문자열의 두번째 문자는 항상 ~이고, 4번째 문자는 <, =, > 중 하나이며 마지막 숫자는 0~6이었던 것 같다. N은 최대 100? 1000? 정도였다.

풀이 : 그냥 단순하게 8! 가지 경우를 전부 검사해보면 된다. stl에 있는 next_permutation 함수를 쓰면 쉽게 할 수 있다. next_permutation 함수의 존재를 몰라도 재귀로 짜거나 8중 for문으로 8^8가지를 검사해도 맞을 수 있다.

#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class constraint{
  public:
    int a, b, type, v;
    //type : 0은 =, 1은 <, 2는 >
    void init(string & s, map<char, int> & mapping)
    {
        a = mapping[s[0]];
        b = mapping[s[2]];
        if(s[3] == '=') type = 0;
        else if(s[3] == '<') type = 1;
        else if(s[3] == '>') type = 2;
        v = s[4] - '0' + 1;
    }
};
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    string ss = "ACFJMNRT";
    map<char, int> mapping;
    for(int i=0;i<ss.size();i++) mapping[ss[i]] = i;
    int answer = 0;
    vector<constraint> cont;
    for(auto & s : data) {
        constraint now; now.init(s, mapping);
        cont.push_back(now);
    }
    vector<int> a(ss.size()); for(int i=0;i<ss.size();i++) a[i] = i;
    do{
        bool isSat = true;
        for(auto & c : cont){
            int diff = abs(a[c.a] - a[c.b]);
            if(c.type == 0){
                if(diff != c.v) isSat = false;
            }
            if(c.type == 1 && diff >= c.v) isSat = false;
            if(c.type == 2 && diff <= c.v) isSat = false;
            if(!isSat) break;
        }
        if(isSat) answer++;
    }while(next_permutation(a.begin(), a.end()));
    return answer;
}

2번. GPS

문제 : 어떤 택시가 움직인 경로가 있는데 오차가 생겨서 경로가 invalid 할 수 있다고 한다. 이 때 경로의 내용을 바꿔 valid한 경로로 만들기 위한 최소 수정 횟수를 구하는 문제이다. 경로의 시작점과 끝점은 바꿀 수 없다. 택시가 운행되는 도시의 정보는 정점 n개, 정점을 잇는 무방향 간선 m개로 이루어진 그래프 형식으로 주어진다. 운행 경로는 택시가 위치했던 정점의 번호가 순서대로 k개 주어진다. n<=200, m<=10000, k<=100이다.

풀이 : 다이내믹 프로그래밍으로 해결할 수 있다. 2차원 dp 테이블의 크기를 n * n으로 잡고 정의를 다음과 같이 두자.

dp[i][j] = 경로의 i번째 위치가 j번 도시가 되면서 i번째 위치까지의 경로가 valid하게 고쳐야 하는 최소 횟수

시작점은 바꿀 수 없기 때문에 base case는 'dp[0][j] = j가 원래 경로의 첫번째 정점이면 0, 그 외엔 INF' 가 된다.

이제 j번 도시가 연결된 도시를 a1, a2, ..., as라고 두면

dp[i][j] = min(dp[i-1][a1], ..., dp[i-1][as], dp[i-1][j]) + (origin[i] == j ? 0 : 1)

이 성립한다. i번째까지의 경로가 valid하기 위해선 i-1번째까지의 경로가 valid하면서 i-1번째 위치가 i번째 위치와 연결되어야 하기 때문이고, 주어진 경로에서 i번째 위치가 j면 그 상태로 두면 되고 아니면 한번 더 고쳐야 하기 때문이다. 택시가 가만히 있는 경우도 허용하기 때문에 dp[i-1][j]도 고려해준다. O(k(n+m))의 시간복잡도로 해결할 수 있다.

#include <vector>
#include <algorithm>
using namespace std;
vector<int> adj[210];
int dp[210][210];
const int inf = 987654321;
void init(vector<vector<int>> edge_list)
{
    for(int i=0;i<210;i++) adj[i].clear();
    for(int i=0;i<210;i++) for(int j=0;j<210;j++) dp[i][j] = inf;
    for(auto & e : edge_list){
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    init(edge_list);
    dp[0][gps_log[0]] = 0;
    for(int i=1;i<k-1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int add = (gps_log[i] == j ? 0 : 1);
            dp[i][j] = min(dp[i][j], dp[i-1][j] + add);
            for(auto p : adj[j]){
                dp[i][j] = min(dp[i-1][p] + add, dp[i][j]);
            }
        }
    }
    answer = inf;
    for(auto p : adj[gps_log.back()]){
        answer = min(answer, dp[gps_log.size()-2][p]);
    }
    if(answer > inf / 2) answer = -1;
    return answer;
}

3번. 리틀 프렌즈 사천성

문제 : m * n 격자가 있고 그 위에 여러 종류의 블록이 있다. 초기 상태에서 각 격자 칸은 비어 있거나, 장애물이 있거나, 서로 구별되는 특별한 블록이 있다. 특별한 블록은 A, B, ..., Z의 대문자 알파벳으로 나타내어 지고 각 블록은 0개거나 2개만 있다. 서로 같은 블록을 최대 한번만 90도로 꺾어서 연결할 수 있는 경로가 있으면 그 블록을 없앨 수 있다. 격자의 초기 상태가 주어질 때, 특별한 블록을 모두 없앨 수 있으면 없애는 순서 중 사전순으로 가장 앞선 문자열을 반환하고, 그럴 수 없으면 IMPOSSIBLE을 반환하라. m, n <= 100.

풀이 : 사라질 수 있는 쌍이 최대 26(=알파벳 대문자의 개수)개 이므로 그리디 + 브루트 포스로 하면 된다. 사전 순으로 가장 앞선 순서를 찾아야 하기 때문에 현재 상황이 있을 때 A부터 Z까지 순서대로 한 쌍씩 없앨 수 있는지 판단해보고 없앨 수 있다면 없앤 다음 A부터 찾는걸 다시 반복하면 된다. 그러다 더 이상 없애는게 불가능하면 남은 특별한 블록이 있는지 검사한 뒤 답을 반환하면 된다.

없앨 수 있는지 검사하는 방법은 다음과 같다. 이번에 없애고 싶은 블록의 위치가 (x1, y1), (x2, y2)라면 가능한 경로는 두가지 (x좌표를 먼저 움직인 뒤 y좌표를 움직이거나 y좌표를 먼저 움직인 뒤 x좌표를 움직이기) 이므로 그냥 O(n * m)에 판단 가능하다. 총 시간복잡도는 O(26*26*n*m). 대충 짜느라 코드가 꽤 길다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
int arr[110][110];
vector<pair<int, int> > pos['Z' + 5];
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
 
bool able(char ch)
{
    if(pos[ch].empty()) return false;
    int x = pos[ch][0].first;
    int y = pos[ch][0].second;
    int nx = pos[ch][1].first;
    int ny = pos[ch][1].second;
    int a = x, b = y;
    bool flag = true;
    while(flag && a != nx){
        if(a > nx) a--;
        else if(a < nx) a++;
        if(a != nx || b != ny){
            if(arr[a][b] != '.') flag = false;
        }
    }
    while(flag && b != ny){
        if(b > ny) b--;
        else if(b < ny) b++;
        if(a != nx || b != ny){
            if(arr[a][b] != '.') flag = false;
        }
    }
    if(flag) return true;
    flag = true; a = x; b = y;
    while(flag && b != ny){
        if(b > ny) b--;
        else if(b < ny) b++;
        if(a != nx || b != ny){
            if(arr[a][b] != '.') flag = false;
        }
    }
    while(flag && a != nx){
        if(a > nx) a--;
        else if(a < nx) a++;
        if(a != nx || b != ny){
            if(arr[a][b] != '.') flag = false;
        }
    }
    if(flag) return true;
    return false;
}
 
string solution(int m, int n, vector<string> board) {
    for(int i=0;i<'Z'+5;i++) pos[i].clear();
    memset(arr, -1, sizeof(arr));
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            arr[i][j] = board[i][j];
            if('A' <= arr[i][j] && arr[i][j] <= 'Z'){
                pos[arr[i][j]].push_back(make_pair(i, j));
            }
        }
    }
    bool flag = true;
    string answer = "";
    while(flag)
    {
        flag = false;
        for(int i='A';i<='Z';i++){
            flag = able(i);
            if(flag) {
                arr[pos[i][0].first][pos[i][0].second] = '.';
                arr[pos[i][1].first][pos[i][1].second] = '.';
                pos[i].clear();
                answer += i; break;
            }
        }
    }
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(arr[i][j] != '.' && arr[i][j] != '*') return "IMPOSSIBLE";
        }        
    }
  
    return answer;
}

4번. 튜브의 소개팅

문제 : 현재 m * n 격자 구조의 방에 파티가 열리고 있다. 튜브는 (0, 0)에서 출발해 (m-1, n-1)에 있는 소개팅 상대를 만나러 가려고 한다. 그런데 각 격자 위에는 장애물이 있거나 파티를 즐기고 있는 튜브의 친구가 있다. 장애물이 있는 칸은 지나갈 수 없고, 튜브의 친구가 있는 칸을 지나가려면 t초동안 친구와 수다를 떨어야 한다. 그런데 친구와 얘기를 나눈 시간이 합해서 s초를 넘어가면 튜브의 인내심이 버티지 못해 미친 오리로 변신하게 되고, 소개팅은 실패하게 된다. 파티장의 상황이 주어졌을 때, 튜브가 미친 오리로 변신하지 않고 갈 수 있는 경로 중 이동거리가 가장 짧은 경로를 찾고, 그 때의 경로 길이와 친구와 얘기를 나눈 총 시간을 각각 구하라. m, n <= 50. 파티장의 상황은 이차원 배열 time_map으로 주어지고 time_map[i][j]가 -1이면 장애물이 있는 것이고, 0 이상이면 (i, j) 칸에 친구가 있으며 그 칸을 지나기 위해선 time_map[i][j] 초만큼 수다를 떨어야 함을 의미한다.

풀이 : 가능한 경로의 길이가 최대 n * m이므로 일반적인 경로 탐색 알고리즘에서 cost를 시간으로 두고 모든 가능한 경로 길이에 대해 계산해보면 된다. 출발점부터 i, j까지 길이 d의 경로로 가는 값을 dist[d][i][j]라고 정의하고 bfs나 다익스트라를 통해 탐색하면 된다. 탐색이 끝난 후 0<=d<=n*m인 모든 d에 대해 dist[d][m-1][n-1]이 s를 넘으면 소개팅은 무조건 실패하고, 그렇지 않다면 그 중 가장 작은 d가 경로의 길이가 되고 dist[d][m-1][n-1]이 수다를 떠는 시간의 합이 될 것이다.

#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
const long long inf = 1987654321LL * 1231231LL;
//dist[d][i][j]는 i, j를 경로 길이 d로 오는 최단 시간
class point {
public:
    int x, y;
    bool operator<(const point & other) const{
        return x == other.x ? y < other.y : x < other.x;
    }
};
long long dist[2510][52][52];
int m, n;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool safe(int a, int b){
    return 0<=a&&a<m&&0<=b&&b<n;
}
bool safe(point a){return safe(a.x, a.y);}
vector<int> solution(int _m, int _n, int s, vector<vector<int>> time_map) {
    m = _m; n = _n;
    for(int i=0;i<2510;i++) for(int j=0;j<52;j++) for(int k=0;k<52;k++) dist[i][j][k] = inf;
    int move_distance = 0;
    int sum_of_talk_time = 0;
    
    queue<pair<point, int> > q;
    point src; src.x = src.y = 0; dist[0][0][0] = 0;
    q.push(make_pair(src, 0));
    while(!q.empty())
    {
        point now = q.front().first;
        int len = q.front().second; q.pop();
        if(len > n * m) continue;
        if(dist[len][now.x][now.y] > s) continue;
        for(int i=0;i<4;i++)
        {
            point next; next.x = now.x + dx[i]; next.y = now.y + dy[i];
            if(!safe(next)) continue;
            if(time_map[next.x][next.y] == -1) continue;
            if(dist[len+1][next.x][next.y] > dist[len][now.x][now.y] + time_map[next.x][next.y]){
                dist[len+1][next.x][next.y] = dist[len][now.x][now.y] + time_map[next.x][next.y];
                q.push(make_pair(next, len + 1));
            }
        }
    }
    for(int i=0;i<=n*m;i++){
        if(dist[i][m-1][n-1] > s) continue;
        move_distance = i;
        sum_of_talk_time = dist[i][m-1][n-1];
        break;
    }
    vector<int> answer(2);
    answer[0] = move_distance;
    answer[1] = sum_of_talk_time;
    
    return answer;
}

5번. 몸짱 트레이너 라이언의 고민

문제 : 트레이너 라이언은 격자 칸 하나를 회원 한명이 사용할 수 있는 n * n 격자로 된 헬스장을 운영하고 있다.  그런데 최근 헬스장 회원들로부터 옆사람과 너무 가까워 헬스장 이용이 불편하다는 불만이 많이 제기되었다. 이에 따라 라이언은 회원 간 간격이 최대한 넓게 되도록 공간을 배정해주려고 한다. 각각의 회원이 헬스장을 이용하는 시간대가 주어질 때, 가능한 회원 간 간격의 최솟값의 최댓값을 구하라. 즉 모든 순간에 유지 가능한 간격의 최댓값을 구하라. 라이언이 헬스장 상황을 고려해 회원의 스케줄을 짜기 때문에 동시간대에 헬스장을 이용하는 회원의 수가 격자칸보다 많은 경우는 없다. 격자 칸의 거리는 상하좌우로 인접한 경우 1, 대각선으로 인접한 경우는 2로 계산한다(=택시기하학). 헬스장은 오전 10시부터 오후 10시까지만 운영하므로 어떤 회원이 헬스장을 이용하는 시간대 (t1, t2)는 600 <= t1 < t2 <= 1320이다. n <= 10이다.

풀이 : 결국 정답은 시간에 상관없이 헬스장에 동시간대에 존재할 수 있는 최대 회원 수에 의해 결정된다. 사람이 제일 많을 때 최적의 경우를 계산해두고 나면 나머지 시간대의 경우 그냥 그 중 아무칸에나 회원을 배치하면 되기 때문이다. 동시간대에 존재하는 최대 사람의 수는 간단한 스위핑으로 해결할 수 있다(solution 함수의 첫 7줄).

이제 n * n 격자에 k명의 사람을 배치할 때 유지 가능한 최대 간격을 구하는 문제를 풀면 된다. 좀 더 생각하기 쉽게 바꾸면, 간격 d와 격자 크기 n이 주어졌을 때 n * n 격자에 최소 d의 간격을 유지하며 사람을 얼마나 배치할 수 있는지를 구하면 된다.

먼저 맨 윗줄에 항상 사람을 배치해야 된다는 것은 생각하기 쉽다. 그렇지 않은 경우 그냥 모든 사람을 한칸 위로 올리면 똑같기 때문. 그런데 맨 왼쪽 위에 사람 한명을 배치한 뒤 배치 가능한 장소 중 (x, y) 값이 가장 작은 장소에 그리디하게 배치하게 하면 딱 한 경우(n = 8, d = 3, 즉 A와 B의 거리가 최소 3이므로 AㅁㅁB는 되고 AㅁB는 안되는 경우)가 생긴다. 

그런데 맨 윗줄에 첫 사람을 배치할 때 맨 왼쪽말고 다른 칸들도 전부 첫번째로 배치한 뒤 똑같은 그리디로 돌려보면 정답이 나온다. 정당성 증명은 헷갈려서 미루고 있는데 문제에서 주어진 n 제한 내에서는 항상 정답이 나온다. 아래는 아까 말한 반례 그림. 그리디 1이 무조건 맨 왼쪽 위에 배치하고 시작하는 것이고, 그리디 2는 맨 윗줄 중 2번째 칸을 먼저 채우고 그리디하게 채우는 방법의 결과이다.

n이 작은 것으로 보아 정해는 브루트 포스 + 적절한 커팅인 것 같다. 실제 대회에서는 그냥 브루트 포스를 돌린 결과를 기록해 둔 뒤 그대로 배열에 적어 제출하거나, 다른 경우는 위의 반례가 있는 그리디로 구한 뒤 반례 하나만 하드 코딩해 제출한 사람이 많은 듯. 

아래 코드에서 gap 값은 풀이의 d값에서 1을 뺀 것과 같은 의미를 가진다. foo에서 맨 윗줄의 어느 칸에 첫 사람을 배치할 지 결정하고 foo2에서 남은 칸을 그리디하게 채운다.

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[110][110];
int foo2(int n, int gap)
{
    int res = 0;
    while (true)
    {
        int x, y;
        bool flag = true;
        for (int j = 0; flag && j < n; j++)
        {
            for (int i = 0; flag && i < n; i++)
            {
                if (arr[i][j] == 0) {
                    res++;
                    x = i; y = j; flag = false; break; 
                }
            }
        }
        if (!flag)
        {
            arr[x][y] = 2;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0;j < n; j++)
                {
                    if (arr[i][j] == 0 && abs(i - x) + abs(j - y) <= gap) arr[i][j] = 1;
                }
            }
        }
        else break;
    }
    return res;
}
int foo(int n, int gap)
{
    int res = 0;
    for(int j=0;j<n;j++){
        memset(arr, 0, sizeof(arr));
        arr[0][j] = 2;
        for(int a=0;a<n;a++)
            for(int b=0;b<n;b++)
                if(abs(a)+abs(b-j)<=gap) arr[a][b] = 1;
        res = max(res, foo2(n, gap) + 1);
    }
    return res;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    int answer = 0;
    vector<int> mark(1330, 0);
    for(auto v : timetable) {mark[v[0]]++; mark[v[1]+1]--;}
    int with = 0, now = 0;//동시에 존재하는 최대 숫자
    for(int i=0;i<mark.size();i++){
        now += mark[i];
        with = max(with, now);
    }
    if(with <= 1) return 0;
    vector<int> gap(30);
    for(int i=0;i<30;i++) gap[i] = foo(n, i);
   // for(auto i : gap) printf("%d ", i); puts("");
    answer = 0;
    while(gap[answer] >= with) answer++;
    return answer;
}

6번. 네오의 귀걸이

문제 : n개의 2차원 점이 주어지고 점들의 x나 y좌표는 겹치지 않는다. 또한 x좌표가 가장 작은 점과 y좌표가 가장 큰 점은 같고, x좌표가 가장 큰 점과 y좌표가 가장 작은 점도 같다. 각각을 S, E로 부른다. 네오는 각 점을 왼쪽 위나 오른쪽 아래 꼭지점으로 가지는 x/y축에 평행한 직사각형들의 순서쌍으로 귀걸이를 만드려고 한다. 첫 직사각형의 왼쪽 위 점은 S, 마지막 직사각형의 오른쪽 아래 점은 E여야 하고 순서에서 A 직사각형 뒤에 B 직사각형이 오면 A의 오른쪽 아래 꼭지점과 B의 왼쪽 위 꼭지점은 동일해야 한다.

각 점에는 특성값 k가 있는데, 이는 해당 점이 직사각형의 오른쪽 아래 점이 될 경우 그 직사각형의 가로+세로 길이(둘레의 절반)가 k가 되어야 함을 의미한다.

n개의 점이 주어졌을 때 만들 수 있는 서로 다른 귀걸이의 개수를 구하라. 또한 초기 상태에서 어떤 점을 더하거나 원래 있던 점을 제거했을 때 만들 수 있는 서로 다른 귀걸이의 개수를 구하라.

n<=100000, 점 추가/삭제 쿼리 n개. 각 쿼리는 누적되지 않는다. 즉 초기 상태에 대해 실행해야 한다. 점을 추가하는 경우 점의 좌표와 특성값이 주어지고, 점을 제거하는 경우 좌표만 주어진다. 좌표값은 -10억 이상 10억 이하이다. 가능한 개수가 매우 클 수 있으므로 10억 7로 나눈 나머지를 출력하라.

풀이 : i번째 점에 대해 S에서부터 출발해 해당 점이 오른쪽 아래 꼭지점이 되는 직사각형 순서쌍의 수를 dp[i], 해당 점에서 출발해 E에서 끝나는 직사각형 순서쌍의 수를 dp2[i]라고 하자. 이 값들을 구할 수 있다면 해당 점을 지나는 답이 되는 직사각형 순서쌍의 수는 dp[i] * dp2[i]로 쉽게 계산할 수 있을 것이다. 전체 순서쌍의 수는 S나 E에 대해서 같은 방식으로 계산해서 구할 수 있다.

이제 해당 테이블들의 점화식을 생각해보자. 만약 i번째 점에 대해 이번 점이 직사각형의 오른쪽 아래 꼭지점이 될 때 왼쪽 위 꼭지점이 될 수 있는 다른 점이 p_1, p_2, ..., p_s고, 왼쪽 위 꼭지점이 될 때 아래쪽 꼭지점이 될 수 있는 다른 점이 q_1, q_2, ..., q_t라면 다음 점화식이 성립한다. 그냥 dp[i]의 경우 S로부터 그 점까지 내려올 수 있는 모든 경우의 수를 구한 것이고, dp2[i]의 경우 E로부터 그 점까지 올라올 수 있는 모든 경우의 수를 구한 것이다.

dp[i] = dp[p_1] + dp[p_2] + ... + dp[p_s]

dp2[i] = dp2[q_1] + dp2[q_2] + ... + dp2[qt_]

이제 가능한 p와 q의 집합을 모두 구하고 각 집합의 dp / dp2 값의 부분합을 빠르게 구하면 문제를 풀 수 있다. 이 때 k값의 의미를 잘 생각해보면 각 점이 속한 x - y = a 꼴의 대각선이 중요함을 알 수 있다. 어떤 점의 좌표가 (a, b)이고 특성값이 k라고 하자. 그럼 그 점이 직사각형의 오른쪽 아래 꼭지점이 된다면 왼쪽 위 꼭지점이 될 수 있는 다른 점의 좌표는 항상 x - y = a - b - k인 직선 위에 있기 때문이다. 또 그 직선위에서도 가능한 후보는 한정된 x좌표에만 존재한다(아래 그림의 오렌지색 선분).

마찬가지로 그 점이 직사각형의 왼쪽 위 꼭지점이 된다면 오른쪽 아래 꼭지점이 될 수 있는 다른 점은 좌표와 특성값 (c, d), s가 a - b = c - d - s를 만족하는 점들이다. 이 특성을 이용해 위의 점화식을 계산할 수 있다.

먼저 핵심 아이디어는 같은 n^2 풀이를 소개한 뒤 nlogn 풀이로 발전시키자.

전처리를 다음과 같이 하자. long long을 key로 가지고 vector<int>를 value로 가지는 map 2개를 각각 p2l, p2l2라고 두자. p2l[a]는 x-y값이 a인 점들의 인덱스를 x좌표 기준으로 정렬한 벡터로, p2l2[a]는 x-y-k값이 a인 점들의 인덱스를 x좌표 기준으로 정렬한 벡터이다. 이제 p2l을 통해 dp 테이블을, p2l2를 통해 dp2 테이블을 계산할 수 있다. 좌표가 (a, b)고 특성값이 k인 i번째 점에 대해 p2l[a - b - k] 벡터에 들어있는 인덱스를 다 순회하며, 그 점이 자신의 왼쪽 위에 있는 경우에만 dp 값을 더해준다. 메모이제이션을 사용하면 O(N^2)으로 갱신할 수 있다. dp2도 p2l2[a-b] 벡터를 순회하며 같은 방식으로 채울 수 있다.

초기 상태에서 답이 ans라고 하자. 그 뒤 점을 추가하는 쿼리가 들어오는 경우 같은 방식으로 그 점에 대한 dp, dp2 값을 계산하고 그 둘을 곱한걸 ans에 더해주면 된다. 점을 제거하는 쿼리가 들어오는 경우 그냥 저장해둔 그 점의 dp, dp2 값을 불러와서 그 둘을 곱한걸 ans에서 빼주면 된다. 아래는 이대로 구현한 O(N^2) 코드이다.

#include <map>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
 
using namespace std;
 
const long long mod = 1000000007;
const long long inf = mod * mod;
const int NSIZE = 200200;
 
 
//dp[i] : i번째 점이 오른쪽 아래 점으로 끝점일 때 시작점에서 오는 경우의 수
int dp[NSIZE];
//dp2[i] : i번째 점이 왼쪽 위 점으로 시작점일 때 끝점까지 가는 경우의 수
int dp2[NSIZE];
map<long long, vector<int> > p2l, p2l2;
bool visit[NSIZE];
long long getdp(int now, int n, vector<vector<int>> & point)
{
    if (visit[now]) return dp[now];
    visit[now] = true;
    long long a = point[now][0], b = point[now][1], k = point[now][2];
    if (p2l.find(a - b - k) != p2l.end())
    {
        vector<int> & line = p2l[a - b - k];
        for (auto next : line) {
            if (point[next][0] < a && point[next][1] > b) {
                dp[now] += getdp(next, n, point); dp[now] %= mod;
            }
        }
    }
    return dp[now];
}
long long getdp2(int now, int n, vector<vector<int>> & point)
{
    if (visit[now]) return dp2[now];
    visit[now] = true;
    long long a = point[now][0], b = point[now][1], k = point[now][2];
    if (p2l2.find(a - b) != p2l2.end())
    {
        vector<int> & line = p2l2[a - b];
        for (auto next : line) {
            if (point[next][0] > a && point[next][1] < b) {
                dp2[now] += getdp2(next, n, point); dp2[now] %= mod;
            }
        }
    }
    return dp2[now];
}
void init(int n, vector<vector<int>> & point)
{
    memset(visit, 0, sizeof(visit));
    memset(dp, 0, sizeof(dp));
    memset(dp2, 0, sizeof(dp2));
    visit[0] = true; dp[0] = 1;
    getdp(n - 1, n, point);
    memset(visit, 0, sizeof(visit));
    visit[n - 1] = true; dp2[n - 1] = 1;
    getdp2(0, n, point);
}
 
vector<int> solution(int n, vector<vector<int>> point, vector<vector<int>> query) {
    assert(point.size() == n);
    sort(point.begin(), point.end(), [](vector<int> a, vector<int> b) {
        if (a[0] != b[0]) return a[0] < b[0];
        if (a[1] != b[1]) return a[1] > b[1];
        return a[2] > b[2];
    });
    p2l.clear(); p2l2.clear();
    for (int i = 0; i<point.size(); i++) {
        auto p = point[i];
        if (p2l.find(0LL + p[0] - p[1]) == p2l.end()) {
            vector<int> temp(1, i); p2l[0LL + p[0] - p[1]] = temp;
        }
        else p2l[0LL + p[0] - p[1]].push_back(i);
        if (p2l2.find(0LL + p[0] - p[1] - p[2]) == p2l2.end()) {
            vector<int> temp(1, i); p2l2[0LL + p[0] - p[1] - p[2]] = temp;
        }
        else p2l2[0LL + p[0] - p[1] - p[2]].push_back(i);
    }
    init(n, point);
    vector<int> answer;
    answer.push_back(dp[n - 1]);
    map<pair<int, int>, int> getkey;
 
    for (auto & p : point) getkey[make_pair(p[0], p[1])] = p[2];
    for (auto & q : query)
    {
        int type; type = q[0];//scanf("%d", &type);
        long long a, b, k; a = q[1]; b = q[2];//scanf("%lld%lld", &a, &b);
        long long pre = 0, nxt = 0;
        if (type == 0) {
            k = q[3];
            if (p2l.find(a - b - k) != p2l.end())
            {
                vector<int> & line = p2l[a - b - k];
                for (auto next : line) {
                    if (point[next][0] < a && point[next][1] > b) {
                        pre += dp[next]; pre %= mod;
                    }
                }
            }
            if (p2l2.find(a - b) != p2l2.end())
            {
                vector<int> & line = p2l2[a - b];
                for (auto next : line) {
                    if (point[next][0] > a && point[next][1] < b) {
                        nxt += dp2[next]; nxt %= mod;
                    }
                }
            }
        }
 
        else {
            vector<int> temp = { q[1], q[2], 1987654321 };
            int pidx = lower_bound(point.begin(), point.end(), temp, [](vector<int> a, vector<int> b) {
                if (a[0] != b[0]) return a[0] < b[0];
                if (a[1] != b[1]) return a[1] > b[1];
                return a[2] > b[2];
            }) - point.begin();
            pre = dp[pidx]; nxt = dp2[pidx];
        }
 
        long long nowans = answer.front();
        if (type == 0) nowans += pre * nxt;
        else nowans -= pre * nxt;
        while (nowans < 0) { nowans += max((2 + (-nowans) / mod) * mod, mod); }
        nowans %= mod;
        answer.push_back(nowans);
    }
    return answer;
}

위의 방식에선 dp나 dp2의 부분합을 구하기 위해 p2l[a-b-k] 벡터나 p2l2[a-b] 벡터를 전부 순회하는데 O(N)의 시간이 걸려 시간복잡도가 커졌는데, 이분탐색과 세그먼트트리(또는 bit)를 사용하면 이 부분을 O(logN)으로 줄일 수 있다. 위의 그림처럼 목표 대각선 위의 점 중 일정 x좌표 구간에서의 합만 구하면 되기 때문에 이분 탐색으로 구간을 찾고, 누적합이나 세그먼트트리 등을 사용해 구간합을 계산하면 된다. x-y값이 작은 점들부터 계산을 시작하면 dp의 경우 누적합만 사용하면 되지만 dp2는 세그먼트트리가 필요하다. 세그트리나 bit 안쓰는 풀이도 있지만 시간복잡도도 같고 구현 난이도도 그렇게 높진 않기 때문에 그냥 세그트리를 썼다.

아래 코드에서 linelu가 p2l과 같은 역할을 하고 linerb가 p2l2와 같은 역할을 한다. map 대신 가능한 모든 x-y, x-y-k 값을 lineVal이라는 배열에 정렬해 넣어 그 배열의 인덱스를 찾아 썼다. rbSum과 luSum2는 필요없는 값이다. 코드 길이가 길긴 한데 중복되는 부분이 많아 실제로는 100줄 정도 적게 짰다.

#include <map>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
 
using namespace std;
 
const long long mod = 1000000007;
const long long inf = mod * mod;
const int NSIZE = 200200;
 
 
class segtree {
public:
    int n;
    vector<long long> tree;
    void clear()
    {
        tree.clear();
    }
    int maxtree(int s, int e, int now) {
        if (s == e) return now;
        return max(maxtree(s, (s + e) / 2, now * 2),
            maxtree((s + e) / 2 + 1, e, now * 2 + 1));
    }
    void init(int _n) {
        n = _n;
        tree.resize(maxtree(0, n, 1) + 10);
        fill(tree.begin(), tree.end(), 0);
    }
    void upd(int p, long long c)
    {
        this->update(0, n, 1, p, c);
    }
    long long update(int s, int e, int now, int p, long long c) {
        if (p < s || e < p) return tree[now];
        if (s == e) {
            return tree[now] = (tree[now] + c) % mod;
        }
        return tree[now] = (update(s, (s + e) / 2, now * 2, p, c) +
            update((s + e) / 2 + 1, e, now * 2 + 1, p, c)) % mod;
    }
    long long qry(int l, int r)
    {
        return this->query(0, n, 1, l, r) % mod;
    }
    long long query(int s, int e, int now, int l, int r) {
        if (r < l) return 0;
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return tree[now] % mod;
        return (query(s, (s + e) / 2, now * 2, l, r) +
            query((s + e) / 2 + 1, e, now * 2 + 1, l, r)) % mod;
    }
};
 
 
//dp[i] : i번째 점이 오른쪽 아래 점으로 끝점일 때 시작점에서 오는 경우의 수
int dp[NSIZE];
//dp2[i] : i번째 점이 왼쪽 위 점으로 시작점일 때 끝점까지 가는 경우의 수
int dp2[NSIZE];
//lineVal[i] : linelu[i]에 속한 점들의 x - y 값
vector<long long> lineVal;
//linelu[i] : x-y가 lineVal[i]인 점들의 인덱스를 x좌표 순으로 정렬한 벡터
vector<int> linelu[NSIZE];
//linerb[i] : 자기가 오른쪽 아래 점일 때 왼쪽 위 점의 x-y가 lineVal[i]가 되어야 하는 점들의 인덱스를 x좌표 순으로 정렬한 벡터 
vector<int> linerb[NSIZE];
//각각 linelu[i]의 dp, dp2 누적합 배열
vector<long long> luSum[NSIZE];
vector<long long> luSum2[NSIZE];
//각각 linerb[i]의 dp, dp2 누적합 배열
vector<long long> rbSum[NSIZE];
segtree rbSum2[NSIZE];
bool visit[NSIZE];
int lupos[NSIZE][2], rbpos[NSIZE][2];
 
 
void init(int n, vector<vector<int>> & point)
{
    memset(dp, 0, sizeof(dp));
    memset(dp2, 0, sizeof(dp2));
    lineVal.clear();
    sort(point.begin(), point.end(), [](vector<int> a, vector<int> b) {
        if (a[0] != b[0]) return a[0] < b[0];
        if (a[1] != b[1]) return a[1] > b[1];
        return a[2] > b[2];
    });
    for (int i = 0; i<NSIZE; i++) {
        linelu[i].clear(); linerb[i].clear();
        luSum2[i].clear(); luSum[i].clear();
        rbSum[i].clear(); rbSum2[i].clear();
    }
    for (int i = 0; i<n; i++)
    {
        lineVal.push_back(0LL + point[i][0] - point[i][1]);
        lineVal.push_back(0LL + point[i][0] - point[i][1] - point[i][2]);
    }
    sort(lineVal.begin(), lineVal.end());
    lineVal.erase(unique(lineVal.begin(), lineVal.end()), lineVal.end());
    int lumin = 987654321;
    for (int i = 0; i<n; i++)
    {
        int idx; long long target = 0;
        target = point[i][0] - point[i][1];
        idx = lower_bound(lineVal.begin(), lineVal.end(), target) - lineVal.begin();
        assert(lineVal[idx] == target);
        linelu[idx].push_back(i);
        lupos[i][0] = idx; lupos[i][1] = linelu[idx].size() - 1;
 
        target = point[i][0] - point[i][1] - point[i][2];
        idx = lower_bound(lineVal.begin(), lineVal.end(), target) - lineVal.begin();
        assert(lineVal[idx] == target);
        linerb[idx].push_back(i);
        rbpos[i][0] = idx; rbpos[i][1] = linerb[idx].size() - 1;
    }
    for (int i = 0; i < NSIZE; i++) rbSum2[i].init(linerb[i].size());
    
    assert(linelu[lupos[0][0]].size() == 1);
    
    dp[0] = 1; luSum[lupos[0][0]].push_back(1);
    for (int i = 0; i<lineVal.size(); i++)
    {
        for (int j = 0; j<linelu[i].size(); j++)
        {
            int now = linelu[i][j];
            long long a = point[now][0], b = point[now][1], k = point[now][2];
            int p = lower_bound(lineVal.begin(), lineVal.end(),
                a - b - k) - lineVal.begin();
            assert(p == rbpos[now][0]);
            if (linelu[p].empty() || k == 1) continue;
            vector<int> temp = { (int)(a - (k - 1)), (int)(b + 1), 0 };
            int l = lower_bound(linelu[p].begin(), linelu[p].end(),
                temp, [&](int tt, vector<int> ss) {
                return point[tt] < ss;
            }) - linelu[p].begin();
            temp = { (int)(a - 1), (int)(b + k - 1), 1987654321 };
            int r = upper_bound(linelu[p].begin(), linelu[p].end(),
                temp, [&](vector<int> ss, int tt) {
                return ss < point[tt];
            }) - linelu[p].begin();
            if (l >= r) continue;
            if (l >= 1) dp[now] = luSum[p][r - 1] - luSum[p][l - 1];
            else dp[now] = luSum[p][r - 1];
            dp[now] = (dp[now] + mod) % mod;
        }
        long long s = 0;
        for (int j = 0; j<linelu[i].size(); j++)
        {
            s += dp[linelu[i][j]];
            s %= mod;
            luSum[i].push_back(s);
        }
    }
    for (int i = 0; i<lineVal.size(); i++)
    {
        long long s = 0;
        for (int j = 0; j<linerb[i].size(); j++)
        {
            s += dp[linerb[i][j]];
            s %= mod;
            rbSum[i].push_back(s);
        }
    }
    assert(linelu[lupos[n - 1][0]].size() == 1);
    dp2[n - 1] = 1; luSum2[lupos[n - 1][0]].push_back(1);
    for (int i = lineVal.size() - 1; i >= 0; i--)
    {
        for (int j = 0; j<linelu[i].size(); j++)
        {
            int now = linelu[i][j];
            long long a = point[now][0], b = point[now][1], k = point[now][2];
            int p = lupos[now][0];
            if (linerb[p].empty()) continue;
            vector<int> temp = { (int)(a + 1), 0, 0 };
            int l = lower_bound(linerb[p].begin(), linerb[p].end(),
                temp, [&](int tt, vector<int> ss) {
                return ss > point[tt];
            }) - linerb[p].begin();
            int r = upper_bound(linerb[p].begin(), linerb[p].end(), b - 1, [&](int bb, int tt) {
                if (bb != point[tt][1]) return bb < point[tt][1];
                else return false;
            }) - linerb[p].begin();
            if (l >= r) continue;
            dp2[now] = rbSum2[p].qry(l, r) % mod;
        }
        long long s = 0;
        for (int j = 0; j<linelu[i].size(); j++)
        {
            s += dp2[linelu[i][j]];
            s %= mod;
            luSum2[i].push_back(s);
        }
        for (int j = 0; j<linelu[i].size(); j++) {
            int now = linelu[i][j];
            rbSum2[rbpos[now][0]].upd(rbpos[now][1], dp2[now]);
        }
    }
 
}
 
vector<int> solution(int n, vector<vector<int>> point, vector<vector<int>> query) {
    assert(point.size() == n);
    init(n, point);
    vector<int> answer;
    answer.push_back(dp[n - 1]);
    int cnt = -1;
    for (auto & q : query)
    {
        cnt++;
        int type; type = q[0];//scanf("%d", &type);
        long long a, b, k; a = q[1]; b = q[2];//scanf("%lld%lld", &a, &b);
        long long pre = 0, nxt = 0;
        if (type == 0) {
            k = q[3];//scanf("%lld", &k);
            int p = lower_bound(lineVal.begin(), lineVal.end(),
                a - b - k) - lineVal.begin();
            if (k != 1 && p < lineVal.size() && lineVal[p] == a - b - k && !linelu[p].empty())
            {
                vector<int> temp = { (int)(a - k + 1), (int)b + 1, 0 };
                int l = lower_bound(linelu[p].begin(), linelu[p].end(),
                    temp, [&](int tt, vector<int> ss) {
                    return point[tt] < ss;
                }) - linelu[p].begin();
                temp = { (int)(a - 1), (int)(b + k - 1), 1987654321 };
                int r = upper_bound(linelu[p].begin(), linelu[p].end(),
                    temp, [&](vector<int> ss, int tt) {
                    return ss < point[tt];
                }) - linelu[p].begin();
                if (l < r) {
                    if (l >= 1) pre = luSum[p][r - 1] - luSum[p][l - 1];
                    else pre = luSum[p][r - 1];
                }
            }
 
            p = lower_bound(lineVal.begin(), lineVal.end(),
                a - b) - lineVal.begin();
            if (p < lineVal.size() && lineVal[p] == a - b && !linerb[p].empty())
            {
                vector<int> temp = { (int)(a + 1), 0, 0 };
                int l = lower_bound(linerb[p].begin(), linerb[p].end(),
                    temp, [&](int tt, vector<int> ss) {
                    return point[tt] < ss;
                }) - linerb[p].begin();
                int r = upper_bound(linerb[p].begin(), linerb[p].end(), b - 1, [&](int bb, int tt) {
                    if (bb != point[tt][1]) return bb < point[tt][1];
                    else return false;
                }) - linerb[p].begin();
                if (l < r) nxt = rbSum2[p].qry(l, r) % mod;
            }
        }
        else {
            vector<int> temp = { q[1], q[2], 1987654321 };
            int pidx = lower_bound(point.begin(), point.end(), temp, [](vector<int> a, vector<int> b) {
                if (a[0] != b[0]) return a[0] < b[0];
                if (a[1] != b[1]) return a[1] > b[1];
                return a[2] > b[2];
            }) - point.begin();
            pre = dp[pidx] % mod; nxt = dp2[pidx] % mod;
        }
 
 
        long long nowans = answer.front();
        pre %= mod; nxt %= mod;
        if (type == 0) nowans += pre * nxt;
        else nowans -= pre * nxt;
        while (nowans < 0) { nowans += (2 + (-nowans) / mod) * mod; }
        nowans %= mod;
 
        answer.push_back(nowans);
    }
    return answer;
}

7번의 경우 그래프이론개론을 듣는 친구가 수업시간에 배운거고 아는 사람은 30분 정도면 짠다더라. 지금 머리가 안돌아가서 생각이 안된다(핑계).

8번은 그냥 너무 어렵다 ㅜㅜ 낸 사람도 신기하고 푼 사람도 신기하다