yukicoder : No.1014 competitive fighting

今回3問ともWriter解と違う解き方してるな…。
https://yukicoder.me/problems/no/1014

問題

N個の技がある。
各技iには発生時間A[i]、威力B[i]、硬直C[i]が設定されている。
技iの次にjを出す場合、A[j]≦B[i]-C[i]でなければならない。
また、同じ技を2回連続出すことはできない。
(別の技を挟めば同じ技を出してもよい)

各技から初めて連続で技を出す場合(2つ目以降は条件を満たす限り任意の技を選択できる)、威力の総和の最大値を求めよ。

解法

Editorialとは別解を使った。
今出してる技を頂点とみなし、次の技への遷移を辺とみなすことを考える。
閉路があれば無限コンボ可能だし、それ以外はDAGとみなして威力の総和の最大値を求めることができる。
ただ、このままだと辺がO(N^2)個できてしまうので何とかしよう。

技をA[i]順にソートすると、ある技の次に出せる技は区間内の頂点群になる。
ただし同じ技を連続して出せないので、区間内に今出す技自体が入っている場合、そこを除いて2つの区間になる。
区間に対する辺を大量に張りたいとき、1区間あたりO(logN)個の辺で済ませるテクは、SegTreeの考えを応用した手法がARC069Dで既出である。
https://img.atcoder.jp/arc069/editorial.pdf

こうすると辺はO(NlogN)個程度になるので、閉路検出なりDAG上のDPなりすればよい。

int N;
int A[101010],B[101010],C[101010];
pair<int,int> P[201010];
int id[101010];


int RL[1<<20],RR[1<<20];
vector<int> E[1<<20];
ll dp[1<<20];
ll X[1<<20];

void add_edge(int cur,int L,int R,int from) {
	if(RR[cur]<=L) return;
	if(R<=RL[cur]) return;
	
	if(L<=RL[cur]&&RR[cur]<=R) {
		E[from].push_back(cur);
	}
	else {
		add_edge(cur*2,L,R,from);
		add_edge(cur*2+1,L,R,from);
	}
}

ll dfs(int cur) {
	if(dp[cur]>=0) return dp[cur];
	if(dp[cur]==-2) return dp[cur]=1LL<<60;
	dp[cur]=-2;
	ll ret=0;
	FORR(e,E[cur]) ret=max(ret,dfs(e));
	return dp[cur]=ret+X[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		P[i]={A[i],i};
	}
	sort(P,P+N);
	FOR(i,1<<19) {
		RL[(1<<19)+i]=i;
		RR[(1<<19)+i]=i+1;
	}
	for(i=(1<<19)-1;i>=1;i--) {
		E[i].push_back(2*i);
		E[i].push_back(2*i+1);
		RL[i]=RL[2*i];
		RR[i]=RR[2*i+1];
	}
	FOR(i,N) {
		id[P[i].second]=i;
	}
	FOR(i,N) {
		y=id[i];
		X[y+(1<<19)]=B[i];
		x=lower_bound(P,P+N,make_pair(B[i]-C[i]+1,0))-P;
		if(x<=y) {
			if(x) add_edge(1,0,x,y+(1<<19));
		}
		else {
			if(y) add_edge(1,0,y,y+(1<<19));
			if(y+1<x) add_edge(1,y+1,x,y+(1<<19));
		}
	}
	
	MINUS(dp);
	FOR(i,N) {
		ll ret=dfs((1<<19)+id[i]);
		if(ret>=1LL<<60) {
			cout<<"BAN"<<endl;
		}
		else {
			cout<<ret<<endl;
		}
	}
	
}

まとめ

ARC069のwriterのcamypaperさんに感謝しつつ解きました。