kmjp's blog

競技プログラミング参加記です

TopCoder SRM 517 Div2 Hard CuttingGrass

最初問題文を読み間違えたけど、後は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11536

問題

N箇所の芝があり、それぞれ初期状態の高さはinit[i]で、以後1日ごとにgrow[i]芝が高くなる。
毎日、grow[i]芝が伸びた後、1か所芝を刈って高さを0にすることができる。
刈った場所は、また翌日からgrow[i]ずつ高くなっていく。

N箇所合計の芝の高さをH以下にできるか、できるなら最短日数を答えよ。

解法

まず、芝はどれだけ伸びても1回で高さ0に出来るので、同じ場所を2回刈る必要はない。
また、刈った後も芝が伸びていくので、高さの総和を抑えるにはgrow[i]が低い順に刈るのが良い。

よって、まずgrow[i]昇順に芝をソートする。
次に、H以下になる目標日数dを0~N日で総当たりする。

各目標日数dについては、DPを用いてN箇所のうちその日数分のみ選択して芝を刈り、合計を最小化していく。
i日目に芝を刈った場所は、d日目には(d-i)*growだけ高くなる。
合計が初めてH以下になった日が答え。
N日芝を刈ってもダメだら、何日経っても達成不可。

O(N^3)で解答可能。

int dpdp[52][52];

class CuttingGrass {
	public:
	int theMin(vector <int> init, vector <int> grow, int H) {
		int N=init.size();
		pair<int,int> P[51];
		int i,d,x,y;
		
		FOR(i,N) P[i]=make_pair(grow[i],init[i]);
		sort(P,P+N);
		
		FOR(d,N+1) {
			ZERO(dpdp);
			FILL_INT(dpdp,1<<29);
			dpdp[0][0]=0;
			FOR(x,N) {
				FOR(y,d+1) {
					dpdp[x+1][y+1] = min(dpdp[x+1][y+1],dpdp[x][y]+(d-(y+1))*P[x].first);
					dpdp[x+1][y] = min(dpdp[x+1][y],dpdp[x][y]+P[x].second+d*P[x].first);
				}
				
			}
			if(dpdp[N][d]<=H) return d;
		}
		return -1;
	}
};

まとめ

先に答えを仮置きし、それを達成可能かチェックする問題はたまにでるね。
DPか二分探索系。