TopCoder SRM 726 Div2 Hard HeroicScheduled2

問題タイトルがヒントになっている。
https://community.topcoder.com/stat?c=problem_statement&pm=14751

問題

N個のタスクがある。
各タスクiは時刻[S[i],T[i]]の間でどこか連続した時間1を消費すれば終えることができる。

N個のタスクの部分集合のうち、適切なタイミングでタスクを行うようにすることで全タスクを完了できるものの総数を求めよ。

解法

区間スケジューリング問題の応用。
まず各タスクを開始時間ごとにまとめよう。

以下、状態として選択したタスク群のうち、未完の物の終了時間の集合をキーとし、その組み合わせを値とするmapを持ってDPを行う。
時間ごとに以下の処理を行おう。

• 今の時間を開始時間とするタスクについて、既存の状態にそのタスクを追加した状態を構築しよう。
  • 全体で時間は16通りしかないので、終了時間の集合はそんなに組み合わせがない。
• 最後に、状態における未完の終了時間のうち一番終了時間が短いものを今の時間で処理したと考える(取り除く)

最終的に空集合をキーとした場合の値を答える。

class HeroicScheduled2 {
	public:
	long long getcount(vector <int> start, vector <int> finish) {
		vector<int> E[16];
		int i,j,mask;
		FOR(i,start.size()) E[start[i]].push_back(finish[i]);
		
		vector<int> V;
		map<vector<int>,ll> M;
		M[V]=1;
		FOR(i,16) {
			FORR(e,E[i]) {
				map<vector<int>,ll> M2=M;
				FORR(m,M) {
					vector<int> v=m.first;
					if(v.size()<16-i) {
						v.push_back(e);
						sort(ALL(v));
						M2[v]+=m.second;
					}
				}
				swap(M,M2);
			}
			map<vector<int>,ll> M3;
			FORR(m,M) {
				vector<int> v=m.first;
				if(v.empty()) {
					M3[v]+=m.second;
				}
				else if(v[0]>=i) {
					v.erase(v.begin());
					M3[v]+=m.second;
				}
			}
			
			swap(M,M3);
		}
		return M[V];
		
	}
}

まとめ

これはDiv2でも解ける人数名いそうだけども、本番正答者がいないのは、そもそも参加者が少なかったからかな。