SRM 387 500pt: IntervalSubsets

TopCoder

問題概要

[start, finish](0

考えたこと

  • 解き方とかはまだ全然分かってないけど、とりあえず半開区間にデータ構造を変換しよう。ユニークもしなくちゃいけないし。
  • 極大と言うのが面倒くさそう。それが無ければDPで行けそうだし。区間の上限100とかもそれっぽい。
    • 今考えたら区間の上限100云々は本質ではなかった(座標圧縮でどうせ50*2=100に落ちるんだし)。
  • えーと、最初に区間をソートしておいて分割統治法でいけそう？
  • でもこれだと、真ん中の区間を選んだときは分割できるけど選ばなかったときに分割もマージも難しい。
  • というか、「最後にカバーされているのがどこか」というのが重要なので、やっぱDPが本筋くさい。
  • 状態は(今いる座標、最後にカバーされた座標、今覆われているかどうか)で行ける？
  • いやいや。最後にカバーされた座標は今いる座標より左側なんだから今覆われているかどうかなんて情報は要らない。
  • だいぶ見えてきた。状態を(今いる座標、最後にカバーされた座標)でDP。状態数O(100^2)。
  • 状態遷移はO(N)位でいけそう。間に区間が含まれてしまったらその状態はinvalidなので遷移を打ちきる。
  • 新たに区間を加えるときは終点までいっきに遷移すれば良い。でもこのときも極大になってるかチェックしなくちゃいけないのでそのチェックはO(N)？ということは全体で遷移の計算量はO(N^2)か。
  • 計算量としてはO(MAX_LEN^2 * N^2)で一応間に合いそうではある。
  • 区間が含まれるとか毎回書いてると読みづらいので関数にする。
  • 書けた。あれ、コンパイル通ってない。uniqueって==を定義しないとダメなのか。
  • コンパイル通ったけどサンプル通らない。調べてみたら重複は別々にカウントするらしい。えーーー。
  • ユニークの部分消したらサンプル通った。提出したら無事通った。

practiceで通ったコード

計算量O(MAX_LEN^2 * N^2)。

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

const int MAX_L = 109;
int dp[MAX_L + 2][MAX_L + 2];

//[from, to)
struct range{
	int from, to;
};

bool operator<(const range& lhs, const range& rhs){
	return make_pair(lhs.from, lhs.to) < make_pair(rhs.from, rhs.to);
}

//aがbに含まれているならtrueを返す
bool is_included(const range& a, const range& b){
	return b.from <= a.from && a.to <= b.to;
}

struct IntervalSubsets {

	int numberOfSubsets(vector <int> start, vector <int> finish) {

		vector<range> rs;
		for(int i=0; i<(int)start.size(); i++){
			rs.push_back((range){start[i], finish[i]+1});
		}

		const int N = rs.size();

		//基底
		dp[0][0] = 1;

		//DP
		for(int cur=0; cur<=MAX_L; cur++){
			for(int last=0; last<=cur; last++){
				//新しく採用する
				for(int i=0; i<N; i++)if(cur == rs[i].from){
					bool ok = true;
					for(int j=0; j<N; j++)if(i!=j){
						ok &= !is_included(rs[j], (range){last, cur});
					}
					if(ok){
						dp[rs[i].to][rs[i].to] += dp[cur][last];
					}
				}

				//新しく採用せずにパス
				bool ok = true;
				for(int i=0; i<N; i++){
					ok &= !is_included(rs[i], (range){last, cur});
				}
				if(ok){
					dp[cur+1][last] += dp[cur][last];
				}
			}
		}

		return accumulate(dp[MAX_L+1], dp[MAX_L+1] + (MAX_L+2), 0);
	}

};