TPC追いコン : C - 鏡餅

こちらも反省点多いな。
http://oidashi.contest.atcoder.jp/tasks/oidashi_c

問題

1～N個の番号の餅が順に与えられる。
各餅は大きさS[i]、色C[i]である。

餅を受け取ると、それらを既存の餅の上に重ねるか、捨てるかを選択できる。
３個餅を重ねた時点で、３つの色が等しく、かつ大きさが降順であるとき、鏡餅が１つ完成したと考える。
（その際重ねた餅は一旦取り除いてよい）

餅を重ねる・捨てるを最適に選択したとき、最大何個鏡餅を作れるか。

解法

x番のお餅が最上位となるような鏡餅のうち、最下段の番号の最大値をf(x)とする。
このf(x)がわかると、x番目までのお餅群で作れる鏡餅数をg(x)とすると、g(x)は以下の簡単なDPで求められる。
g(x) = max(g(x-1), g(f(x)-1)+1)

f(x)はSegTreeを2つ作ってRange Maximum Queryで求められる。
1つは、最下段の餅の大きさに応じた最下段のお餅の番号の最大を管理するもの。
もう一つは、２段目の餅の大きさに応じた最下段のお餅の番号の最大を管理するもの。

餅の色ごとに大きさを座標圧縮し、上記２つのSegTreeを使い以下を求めたり更新したりしよう。

• x番が２段目に来るなら、１段目は同じ色でS[x]以下の大きさの餅のうち、番号が最大のものを選ぶ。
• x番が最上位に来るなら、２段目は同じ色でS[x]以下の大きさの餅のうち、最下段の番号が最大のものを選ぶ。

int N;
int S[101010];
int C[101010];
vector<int> MP[101010];

int st[101010],len[101010];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int pre[101010],did[101010];
SegTree_1<int,1<<20> seg[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(st);
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		cin>>C[i];
		MP[C[i]].push_back(S[i]);
	}
	x = 0;
	FOR(i,101000) {
		MP[i].push_back(0),MP[i].push_back(1<<30);
		sort(ALL(MP[i]));
		MP[i].erase(unique(ALL(MP[i])),MP[i].end());
		st[i]=x;
		len[i]=MP[i].size();
		x+=len[i];
	}
	FOR(i,N) {
		S[i]=lower_bound(ALL(MP[C[i]]),S[i])-MP[C[i]].begin();
		did[i+1]=did[i];
		pre[i]=seg[0].getval(st[C[i]]+S[i]+1,st[C[i]]+len[C[i]]);
		x=-1;
		if(pre[i]>0) {
			x=seg[1].getval(st[C[i]]+S[i]+1,st[C[i]]+len[C[i]]);
			if(x>0) {
				x--;
				did[i+1]=max(did[i+1],did[x]+1);
			}
			seg[1].update(st[C[i]]+S[i],pre[i]);
		}
		seg[0].update(st[C[i]]+S[i],i+1);
		
		
	}
	
	cout<<did[N]<<endl;
}

まとめ

鏡餅問題は門松列問題よりは扱いやすそう。