読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2016 Asia Tsukuba Regional, C 解法

C: Distribution Center

問題

n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。xjは互いに異なる。
ロボットを好きなタイミングで動かしたり止めたりして良いとき、各ラインには何種類の製品を流すことができるか。

解法

製品は隣にしか移動しないので、各ラインに流すことのできる製品は連続した番号であることが分かる。各ラインが取ることのできる範囲の最大値と最小値をもち、ロボットをx座標降順にならべ、隣り合うラインの範囲を互いに広げていく。

コード

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)


int N, M;
pair<int, int> P[100111];

int L[200111], R[200111];

int main() {

    scanf("%d%d", &N, &M);
    REP (i, M) scanf("%d%d", &P[i].first, &P[i].second), P[i].second--;
    sort(P, P+M);

    REP (i, N) L[i] = R[i] = i;

    REP (i, M) {
	int y = P[i].second;
	R[y] = R[y+1];
	L[y+1] = L[y];
    }

    REP (i, N) printf("%d%c", R[i] - L[i] + 1, i==N-1? '\n': ' ');

    return 0;
}

感想

Impractically Complicated Products Corporationの作る製品とは。