Codeforces Round #103 (Div. 2) E : Competition

問題概要

N*N(N<10^5)のボードの右下半分を考える。M(<10^5)のマスに選手がいる(重複なし)。選手は1秒に1マスもっとも近い対角線を目指して動く。任意の時刻で同じマスに同じ選手がいないように最大で何人選手を選べるか求める問題。

解法

r,cを辞書順にソートして貪欲に小さい方に詰めていけばよい。最も小さいところを選ぶのにはBITやsetなどの適切なデータ構造を用いれば対数時間程度で求めることができる。

acceptされたコード

計算量O(M* (log M + log N) )。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 1e5;
const int MAX_M = 1e5;

struct man{
	int r, c, id;
};

int N, M;
man men[MAX_M];

struct BinaryIndexedTree{

	typedef int bit_t;

	static const int MAX_BIT = MAX_N + 1;
	bit_t data[MAX_BIT+1];
	int SIZE;

	void init(int size){
		memset(data, 0, sizeof(data));
		SIZE = size;
	}

	bit_t sum(int n){
		bit_t ret = 0;
		for(;n;n-=n&-n){
			ret += data[n];
		}
		return ret;
	}

	bit_t sum(int from, int to){
		return sum(to)-sum(from);
	}

	void add(int n, bit_t x){
		for(n++;n<=SIZE;n+=n&-n){
			data[n]+=x;
		}
	}

	int get(int k){
		int p = 1<<(31 - __builtin_clz(SIZE));
		for(int q=p; q>0; q>>=1, p|=q){
			if(p > SIZE || k < data[p]){
				p ^= q;
			}
			else{
				k -= data[p];
			}
		}
		return p;
	}
};

BinaryIndexedTree bitree;


void init(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		men[i] = (man){x, y, i+1};
	}
}

bool operator<(const man& lhs, const man& rhs){
	return lhs.r != rhs.r ? lhs.r < rhs.r : lhs.c < rhs.c;
}

void solve(){
	vector<int> ans;

	sort(men, men + M);

	bitree.init(N + 1);
	for(int i=0; i<=N; i++){
		bitree.add(i, 1);
	}

	for(int i=0; i<M; i++){
		int mini = N - men[i].c + 1, maxi = mini + (men[i].r + men[i].c - N - 1);
		int empty = bitree.sum(mini, maxi + 1);
		if(empty > 0){
			int s = bitree.sum(mini);
			int a = bitree.get(s);
			bitree.add(a, -1);
			ans.push_back(men[i].id);
		}

	}

	printf("%d\n", (int)ans.size());
	for(int i=0; i<(int)ans.size(); i++){
		printf("%d%c", ans[i], i==(int)ans.size()-1?'\n':' ');
	}
}

int main(){
	init();
	solve();

	return 0;
}