UVa-10273, ZOJ-1236 : Eat or not to Eat?

問題概要

牛がN(<1000)匹いる。各牛は毎日ある量の牛乳を出す。量はある周期T(<=10)にしたがって変化する。毎日、最も牛乳を出した量が最も少ない牛がユニークにいたらその牛は取り除かれる。繰り返した時に残る牛の数を求める問題。

解法

愚直にシミュレーションする。LCM(1..10)=2520日経っても取り除かれなかったらもう終了してよい。どの辺にグラフの要素があるのかは謎。

acceptされたコード

計算量不明。

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

const int TERM = 2520;
const int MAX_N = 1000;
const int MAX_T = 10;
const int INF = 1<<29;

int live[TERM];
int ts[MAX_N];
int product[MAX_N];
bool is_live[MAX_N];
int Ms[MAX_N][MAX_T];
int N;

int read_int(){
	int x;
	scanf("%d", &x);
	return x;
}

void init(){
	N = read_int();

	fill(live, live+TERM, -1);
	fill(is_live, is_live+N, true);

	for(int i=0; i<N; i++){
		ts[i] = read_int();
		for(int j=0; j<ts[i]; j++){
			Ms[i][j] = read_int();
		}
	}
}

void solve(){
	int cur = N, last_day = 0;

	for(int loop=0; ; loop++){
		for(int day=0; day<TERM; day++){
			if(live[day] == cur){
				printf("%d %d\n", cur, last_day);
				return ;
			}
			else{
				live[day] = cur;
			}

			fill(product, product+N, INF);
			for(int i=0; i<N; i++)if(is_live[i]){
				product[i] = Ms[i][day%ts[i]];
			}

			int *p, *q;
			int tmp;
			p = min_element(product, product+N);
			if(*p == INF){
				printf("%d %d\n", cur, last_day);
				return ;
			}
			tmp = *p;
			*p = INF;
			q = min_element(product, product+N);
			if(*q != tmp){
				is_live[p-product] = false;
				cur--;
				last_day = loop * TERM + day + 1;
			}
		}
	}
}

int main(){
	for(int T = read_int(); T--; ){
		init();
		solve();
	}

	return 0;
}