kmjp's blog

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

第4回 ドワンゴからの挑戦状 予選 : D - ディスクの節約

Dの方がCより簡単じゃない?
https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_d

問題

N個のタスクがある。
i番目のタスクを実行すると、X[i] MBのデータがディスクに書かれた状態になる。

各タスクは、自身より大きな番号のいくつかのタスクに依存している可能性がある。
その場合、依存先タスクの結果がすべてディスクに書かれていた状態でないとタスクを実行できない。
なお、不要なタスクはディスク領域と合わせて削除することができる。

1番のタスクを実行するのに必要な瞬間最大容量の最小値はいくらか。

解法

二分探索+BitDPで解く。
解の候補を二分探索し、ディスク消費量の総和がその解を超えない範囲で、BitDPの要領でとりえる状態を網羅していこう。
ダイクストラでも行けるかもね。

int N;
int X[2020];
int S[1<<20];
int P[20];
int D[20];
vector<int> E[20];
int vis[1<<20];

int ok(int v) {
	ZERO(vis);
	queue<int> Q;
	vis[0]=1;
	Q.push(0);
	
	while(Q.size()) {
		int mask=Q.front();
		Q.pop();
		if(mask&1) return 1;
		
		int i;
		FOR(i,N) if(vis[mask^(1<<i)]==0) {
			if(mask&(1<<i)) {
				vis[mask^(1<<i)]=1;
				Q.push(mask^(1<<i));
			}
			else if((mask&D[i])==D[i] && S[mask^(1<<i)]<=v) {
				vis[mask^(1<<i)]=1;
				Q.push(mask^(1<<i));
			}
		}
	}
	return 0;
	
	
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	for(i=1;i<N;i++) {
		cin>>P[i];
		P[i]--;
		E[P[i]].push_back(i);
		D[P[i]] |= 1<<i;
	}
	int mask;
	FOR(mask,1<<N) {
		FOR(i,N) if(mask&(1<<i)) S[mask] += X[i];
	}
	
	int mi=(1<<28);
	for(i=27;i>=0;i--) {
		if(ok(mi-(1<<i))) mi-=1<<i;
	}
	cout<<mi<<endl;
}

まとめ

いまいち意図がわからない問題だった。