G4 1186 직사각형 색칠하기

보자마자 빡빡한 구현일 것을 직감하였다. 하지만 이런 쉬운 난이도에 빡구현인 문제는 왜 이렇게 하기 싫은걸까..
다른 분들 코드도 구글링해 보았는데 1개 밖에 못 찾았고 그 분은 빡구현으로 하신 듯 했다.
괜히 효율적으로 코딩하고 싶은 마음이 들어서 삽질을 해 보았고 그나마 괜찮은 구현을 했다.

1. 모든 x들과 y들을 각각 배열에 넣어서 정렬 및 중복 값을 제거해준다.
   (참고로 x,y의 최대 개수는 직사각형이 50개이고, 모든 x,y값들이 중복되지 않는다고 했을 때 직사각형 당 2개를 갖고 있으니 총 100개가 된다.)
2. 그러면 최대 100 x 100 grid가 나오는 데 각 grid에 대한 너비를 미리 계산하여 배열에 저장한다.
3. 각 직사각형마다 해당 직사각형의 grid 좌표인 grid_x1, grid_y1, grid_y2, grid_y2를 저장해 놓는다.
   해당 직사각형의 넓이를 구하고 싶으면 grid_x1 ~ grid_x2-1과 grid_y1 ~ grid_y2-1에 대한 grid 너비를 모두 합하면 된다.
   맨 마지막 좌표를 빼는 이유는 (i,j)에 대한 grid의 넓이를 계산할 때 (x[i+1]-x[i]) * (y[i+1]-y[i])를 저장했기 때문. 자세한 건 코드를 보면서 참고
4. 직사각형 높은 번호부터 영역 넓이를 계산하고 사용한 grid는 visit 처리해준다. 그럼 그 다음 직사각형은 해당 grid를 제외하고 너비를 계산하다.
5. 이런 식으로 계산한 너비를 1) 넓이가 큰 순으로, 2) index가 낮은 순으로 정렬한 후 앞의 K개만큼 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

bool used[100][100];
int gridX[100], gridY[100];
vector<int> xval, yval;

class rectangle {
public:
    int idx;
    int x1, y1, x2, y2;
    int grid_x1, grid_y1, grid_x2, grid_y2;
    int area;

    void set_grid() {
        grid_x1 = lower_bound(all(xval), x1) - xval.begin();
        grid_x2 = lower_bound(all(xval), x2) - xval.begin();
        grid_y1 = lower_bound(all(yval), y1) - yval.begin();
        grid_y2 = lower_bound(all(yval), y2) - yval.begin();
    }
    void paintArea() {
        this->area = 0;
        for(int x=grid_x1; x<grid_x2; x++) {
            for(int y=grid_y1; y<grid_y2; y++) {
                if (used[x][y]) continue;
                used[x][y] = true;
                this->area += gridX[x] * gridY[y];
            }
        }
    }
};
bool cmp(rectangle a, rectangle b) {
    if(a.area == b.area) return a.idx < b.idx;
    return a.area > b.area;
}

int N, K;
vector<rectangle> recs;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(used, 0, sizeof used);

    cin >> N >> K;
    recs.resize(N);
    for(int i=0; i<N; i++) {
        recs[i].idx = i+1;
        cin >> recs[i].x1 >> recs[i].y1 >> recs[i].x2 >> recs[i].y2;
        xval.emplace_back(recs[i].x1); xval.emplace_back(recs[i].x2);
        yval.emplace_back(recs[i].y1); yval.emplace_back(recs[i].y2);
    }
    sort(all(xval)); sort(all(yval));
    xval.erase(unique(all(xval)), xval.end());
    yval.erase(unique(all(yval)), yval.end());
    for(int i=1; i<xval.size(); i++) {
        gridX[i-1] = xval[i] - xval[i-1];
    }
    for(int i=1; i<yval.size(); i++) {
        gridY[i-1] = yval[i] - yval[i-1];
    }

    for(int i=0; i<N; i++) {
        recs[i].set_grid();
    }
    for(int i=N-1; i>=0; i--) {
        recs[i].paintArea();
    }

    vector<int> ans;

    sort(all(recs), cmp);
    for(int i=0; i<K; i++) {
        ans.emplace_back(recs[i].idx);
    }
    sort(all(ans));
    for(int x : ans) {
        cout << x << ' ';
    }
    cout << '\n';

    return 0;
}

G3 7570 줄 세우기

수들이 연속적인 부분수열이면서 동시에 LCS인 수열을 찾으면 된다. 이를 연속적인 LCS라 부르겠다.
예를 들면, [1, 2, 3, 5, 6, 4] 인 수열이 주어졌을 때 기존 LCS는 [1, 2, 3, 5, 6]이 될 것이다.
하지만 우리가 찾아야할 것은 LCS이면서 수들이 연속적이어야 하므로 [1, 2, 3, 4]가 연속적인 LCS가 된다.

연속적인 LCS를 찾아야 하는 이유를 알아보자.
주어진 수열은 [1, 2, ... , N]이고, 연속적인 LCS가 [a, a+1, a+2, ..., b] 라고 하자.
그렇다면 주어진 수열에서 a보다 작은 수들은 a-1부터 1의 순서로 맨 앞으로 보내고,
b보다 큰 수는 b+1부터 N의 순서로 맨 뒤로 보낸다.

따라서 정답은 N - [연속적인 LCS의 길이] 가 된다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
#define all1(v) (v).begin()+1, (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

int N;
vector<int> idx;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    idx.resize(N+1);
    for(int i=1; i<=N; i++) {
        int val; cin >> val;
        idx[val] = i;
    }
    int longest = 0, val, prob;
    for(val = 1, prob = 1; val < N; val++, prob++) {
        if(idx[val] > idx[val+1]) {
            longest = max(longest, prob);
            prob = 0;
        }
    }
    cout << N - max(longest, prob) << '\n';


    return 0;
}

P5 10217 KCM Travel

1시간 4분 7초
우선순위 큐 다익스트라인데 우선순위 큐를 큐로 바꾸면 풀리는 문제다.
(이전에는 우선순위큐도 통과되었던 듯 하다.)

그 이유를 도저히 모르겠어서 백준 질문게시판을 다 찾아보고 구글링도 해봤는데 아직도 확실히는 모르겠다.
대체적인 이유는 일반적인 최소 경로 탐색 문제와는 다르게 조건이 있어서 worst case의 경우 모든 Edge의 수가 $M \times K$ 가 되어버린다.
비용을 매번 초과해버리는 경우 노드를 M번 방문하게 되고 방문할 때마다 또 다시 모든 edge를 방문하게 되므로 총 Edge의 수는 $M \times K$가 되어버린다.
따라서 우선순위큐 시간복잡도가 $O(ElogE)$인데 E = MK = 10^8 이므로 시간초과가 되어버리는 듯 하다.
반면에 큐는 거리가 적은 순으로 정렬하지 않기 때문에 우직하게(?) 탐색하고 worst case를 만나지 않는 듯 하다.

조금 더 추측해보자면,
입력으로 주어지는 테스트케이스들 중 몇 개의 데이터셋이 우선순위 큐에서 worst-case를 무조건적으로 발생시키는 dataset이라고 하자.
이것이 큐로 했을 때 우선순위 큐보다 worst-case를 만날 확률이 낮을 수 밖에 없다. 아마도 백준의 채점 데이터셋에서 몇 개의 인풋들에 대하여 우선순위 큐가 큐에 비해 압도적으로 worst한 case들을 갖는 것 같다. 30%대의 인풋들을 의심해본다

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

const int MXN = 101;
const int COST_MXN = 1e4+1;
queue<ti3> q; // init complete
int N, M, K; // init complete
vector<ti3> g[MXN]; // g[here] := (there, 비용, 거리)  init complete
int dist[MXN][COST_MXN]; // init complete

// start = 1, end = N
string dijkstra() {
    int ans = INF;
    dist[1][0] = 0; // dist[위치][비용] := 거리
    q.emplace(0, 0, 1); // (거리, 비용, 위치)
    while(!q.empty()) {
        int hereDist = get<0>(q.front()), hereCost = get<1>(q.front()), here = get<2>(q.front());
        q.pop();
        if(here == N) ans = min(ans, hereDist);
        if(dist[here][hereCost] < hereDist) continue;
        for(ti3 edge : g[here]) {
            int there = get<0>(edge), thereCost = hereCost + get<1>(edge), thereDist = hereDist + get<2>(edge);
            if(thereCost > M) continue;
            if(dist[there][thereCost] <= thereDist) continue;
            dist[there][thereCost] = thereDist;
            q.emplace(thereDist, thereCost, there);
        }
    }
    if(ans == INF) return "Poor KCM";
    return to_string(ans);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T; cin >> T;
    while(T--) {
        cin >> N >> M >> K;

        // init
        for(int i=1; i<=N; i++) vector<ti3>().swap(g[i]); // init g
        while(!q.empty()) q.pop(); // init q
        fill(&dist[0][0], &dist[MXN-1][COST_MXN], INF); // init dist

        while(K--) {
            int u, v, c, d; cin >> u >> v >> c >> d;
            g[u].emplace_back(v,c,d);
        }

        cout << dijkstra() << '\n';
    }


    return 0;
}