Autumn Fest 2012 : A Irregular Contest

SRM,ARCに続きAutumn Festにも出ていました。
結果は○○○－△△－－△△－と、後半ではLargeが全然解けず、Smallをかき集める羽目に。
計算量を落とすデータ構造やアルゴリズムの知識が足りないので、勉強していきます。

まずは１問目。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_01

いくつかの大問について、部分点とかかる時間の集合が与えられる。
少ない部分点から順に取り組んだとき、最終的に得られる点を答える。

最初「時間内に得られる最高点」を求めると勘違いし、いきなりDPか…と思ったけど違ったようだ。
DPを書ききってから直したので、おかげで30分以上かかってしまった。

int N,TT;
int P[30];
int S[30][10];
int T[30][10];

int F[30];

void solve() {
	int x,y,i,j,p,rr,TM,TTC;
	
	GET2(&N,&TT);
	FOR(i,N) P[i]=GETi();
	FOR(x,N) FOR(y,P[x]) S[x][y]=GETi();
	FOR(x,N) FOR(y,P[x]) T[x][y]=GETi();
	
	rr=0;
	ZERO(F);
	while(TT>0) {
		int mins=99999,mint=99999;
		int minp=0;
		
		FOR(i,N) {
			if(F[i]>=P[i]) continue;
			if(S[i][F[i]] < mins) {
				mins=S[i][F[i]];
				minp=i;
				mint=T[i][F[i]];
			}
		}
		if(TT<mint) break;
		TT-=mint;
		if(F[minp]==0) rr+=S[minp][F[minp]];
		else rr+=S[minp][F[minp]]-S[minp][F[minp]-1];
		F[minp]++;
	}
	
	_P("%d\n",rr);
	return;
}

まとめ

最近問題文をちゃんと読まず苦労しているので、ちゃんとしないとね。