SRM,ARCに続きAutumn Festにも出ていました。
結果は○○○-△△--△△-と、後半ではLargeが全然解けず、Smallをかき集める羽目に。
計算量を落とすデータ構造やアルゴリズムの知識が足りないので、勉強していきます。
まずは1問目。
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; }
まとめ
最近問題文をちゃんと読まず苦労しているので、ちゃんとしないとね。