TopCoder SRM 676 Div1 Hard Farmville

作問側の計算量見誤り？
https://community.topcoder.com/stat?c=problem_statement&pm=13952

問題

N個の植物を育てたい。
一部の植物は、前提として依存する植物が全て先に育ちきってないと育て始めることができない。
この依存関係は行列Sで与えられる。(なお依存関係は循環しないことが保証されている)

各植物iは、育て始めてから育ちきるまで時間T[i]かかる。
ただしお金をC[i]掛け肥料を与えることでかかる時間を1減らすことができる(ただし当然時間は負にはできない)。
総額Bのお金が利用できるとき、全植物が育ちきるまでかかる最短時間を求めよ。

解法

この問題はTが小さい。
よって、「時間を1減らすにはどの植物群の時間を減らすのがよいか？」をN*T[i]回求めればよい。
これは実質最小カットのうち総コスト最小のものを求めるのと同じである。

まず処理を容易にするために、「他のすべての植物に依存し、かつT[i]=0」の植物を末尾に追加しよう。
そうするとこの問題はこの植物の育つ最短時間を求める問題に置き換えられ、コードもシンプルになる。

植物は依存関係に応じてトポロジカルソートする。
そして「時間を1減らすにはどの植物群の時間を減らすのがよいか？」の候補を求めていこう。
他の回答者はグラフを作成し、最小カットを求めていたようだ。
こちらは別の手法で求めていく。

この過程では以下の３つパラメータを管理していく。

• CT[i]: 現状植物iが育ちきるまでの最短時間
• mask[i]: この植物が育つ時間を最小コストで1減らすのに必要な、減らすべき植物群のbitmask
• CO[i]: 上記mask[i]に対応する植物群のコストの総和

まずCTについて以下が成り立つ。
CT[i] = T[i] + max(依存する植物jにおけるCT[j])
よってCT[i]を1減らすには、T[i]を1減らすか、CT[j]がmaxとなるようなCT[j]群をすべて1減らす必要がある。

後者を達成するには、そのようなjに対してCO[j]の総和を求める…と、依存関係が菱形になっている場合同じ植物を複数回カウントしてしまう。
よってそうではなく、そのようなjに対しmask[j]のbitwise orを取りコストを掛け時間を減らすべき植物群を求めよう。
そのようなmask[j]のbitwise orで得られるコストと、cost[i]の小さい方がCO[i]となる。
(T[i]がすでに0なら、T[i]を減らす選択肢は取れないことに注意)

末尾に追加した植物に対しCO[N]≦(残金)なら、mask[N]に対応する植物の時間を1ずつ減らす。
あとは残金またはT[i]が残っている限りこの処理を繰り返せばよい。
以下のコードはO(N^3*max(T))で最大ケースでも14msで通った。

class Farmville {
	public:
	int N;
	
	int minTime(vector <string> s, vector <int> time, vector <int> cost, int budget) {
		int x,y,z,i;
		N=s.size();
		
		FOR(y,N) s[y]+="0";
		s.push_back(string(N,'1')+"0");
		
		time.push_back(0);
		cost.push_back(0);
		
		N++;
		
		int vis[100]={};
		FOR(y,N) FORR(r,s[y]) r-='0', vis[y]+=r;
		
		vector<int> T;
		FOR(i,52) {
			FOR(x,N) if(vis[x]==0) {
				T.push_back(x);
				FOR(y,N) if(vis[y]>0 && s[y][x]) vis[y]--;
				vis[x]=-1;
			}
		}
		
		ll ct[52];
		FOR(i,25*52) {
			ll dep[52]={}, co[52]={};
			FOR(x,N) {
				int r=T[x];
				
				ct[r]=0;
				FOR(y,N) if(s[r][y]) {
					if(ct[y]==ct[r]) dep[r] |= dep[y];
					else if(ct[y]>ct[r]) {
						ct[r]=ct[y];
						dep[r]=dep[y];
					}
				}
				co[r]=0;
				FOR(y,N) if(dep[r] & (1LL<<y)) co[r] += cost[y];
				
				if(time[r] && ((cost[r]<co[r]) || dep[r]==0)) {
					dep[r] = 1LL<<r;
					co[r]=cost[r];
				}
				else if(dep[r]==0) {
					co[r]=1LL<<40;
				}
				
				ct[r]+=time[r];
			}
			
			if(co[N-1]>budget || dep[N-1]==0) break;
			budget-=co[N-1];
			FOR(y,N) if(dep[N-1] & (1LL<<y)) time[y]--;
		}
		
		return ct[N-1];
	}
}

まとめ

トイレ行ってなければ通ってたかも…。