第二回ドワンゴからの挑戦状予選

出ました.7位でした.はまらずにEの部分点まで解けて予選通過できてよかった(あとで順位表見たらちょっとでもはまってたらダメそうだった)

A:全部25の倍数.コンパイルせずに出したけどFAじゃなかった,かなC
B:左右のどっちかの数字以外にする意味はなくて,どっちにするかと言われるとでかい方だと矛盾しちゃうので小さい(大きくない)ほうならOK.矛盾判定もこれでできる.
C:こういう系頭がこんがらがるので苦手なんだけど,後ろからダイクストラをするみたいな解法で解ける.自分は二分探索をした.答えがT以下か?という質問に対しては,普通に始点からダイクストラするんだけど,辺を使って良い条件として,「ここでミスった時にもT以下で着ける」が必要十分.ミスった時ほげみたいなのは事前に終点からダイクストラすればわかる.
単調性からトポロジカル順序でないものに対しうまく順番を決めていくというのダイクストラの本質で,前者の解法はそれをちゃんとわかってないと解けない気がする(ちなみにAOJ1178 壊れたドアが類題).
D:長方形を描いてみると縦線か横線のどっちかで2つの長方形を分断できることがわかり,逆にそう分断できるような2つの長方形なら書いてもいいことがわかるので,左a列の中でのmax長方形みたいなのを合わせてO(N^3)で求めればOK.
E:部分点は愚直なDP minをとるのが[0,i)みたいな部分なので更新も合わせてO(N^2)になる.
満点解法は,まず今のdpに対しval[i]=dp[i+1]-dp[i] と差分を考える.こうすると花火に対して-1,..-1,1....1みたいなのを足せばいいことがわかる.時間が過ぎると右からのminで均されるんだけど,差分を持っとくと(dpの凸性から)差分がはじめて0になったとこより右の差分を全部0にすればいいことがわかる.なので,区間add,点val,区間assignができるsegtreeを持てばいいです.→最後のやつのせいで遅延評価が必要になる気がして面倒
実は考察をするともう一段階楽になって,同じ時間に生える花火は,遠くの方から順番に生えてる花火だとしても同じことになる(∵単調減少するような花火列の途中で進む意味は全く無い(それならその前に進むほうが絶対に良い)ことから,途中で動けないとしてよい).よってやるべきことは-1..-1,1...1を足して0より右を0にする,を毎回やることなんだけど,これ毎回やってると,足した後に0より大きいところは1しか出てこなくて,その部分をはなから足さなければいいということがわかる.これで区間assignが要らなくなって,簡単なsegtreeで解けるようになります.

凸に気づき(流石に前提),1次関数なので差分を取り(典型力),考察により楽になる(これはむずいけどデータ構造で殴るでも可) という問題で,色んな要素が詰まった良問だと思う.設定も綺麗だしdegwerすごい.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll inf=1e11;
typedef pair<int,ll> P;
struct edge{
	int to,mis;
	ll c,mc;
	edge(int a,int b,ll c,ll d) :to(a),mis(b),c(c),mc(d){}
};
vector<edge> G[25252];
int N,M,s,t;
int tmp[25252],tc[25252];
ll d0[25252],d[25252];
void dijkstra(ll T){
	rep(i,N) d[i]=inf;
	d[s]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
	while(!que.empty()){
		P p=que.top();que.pop();
		int v=p.sc;
		if(d[v]<p.fs) continue;
		for(edge e:G[v]) if(d[v]+e.mc+d0[e.mis]<=T){
			if(d[e.to]>d[v]+e.c){
				d[e.to]=d[v]+e.c;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}
int main(){
	cin>>N>>M>>s>>t;
	rep(i,M){
		int L;
		cin>>L;
		rep(i,L) cin>>tmp[i];
		rep(i,L-1) cin>>tc[i];
		ll sum=0;
		for(int i=L-2;i>=0;i--){
			sum+=tc[i];
			G[tmp[i]].pb(edge(tmp[i+1],tmp[L-1],tc[i],sum));
		}
		sum=0;
		for(int i=1;i<=L-1;i++){
			sum+=tc[i-1];
			G[tmp[i]].pb(edge(tmp[i-1],tmp[0],tc[i-1],sum));
		}
	}
	rep(i,N) d0[i]=inf;
	d0[t]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,t));
	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v=p.sc;
		if(d0[v]<p.fs) continue;
		for(edge e:G[v]){
			if(d0[e.to]>d0[v]+e.c){
				d0[e.to]=d0[v]+e.c;
				que.push(P(d0[e.to],e.to));
			}
		}
	}
	ll ub=1e10,lb=0;
	while(ub-lb>1){
		ll T=(ub+lb)/2;
		dijkstra(T);
		if(d[t]<=T) ub=T;
		else lb=T;
	}
	cout<<ub<<endl;
}

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll x[300][300];
ll tmp[300][300],u[300],d[300];
ll inf=1e10;
ll ans=-inf;
int H,W;
int main(){
	cin>>H>>W;
	rep(i,H) rep(j,W) cin>>x[i][j];
	rep(i,H){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		u[i]=mx;
	}
	rep(i,H-1) chmax(u[i+1],u[i]);
	rep(i,W) rep(j,W) tmp[i][j]=0;
	for(int i=H-1;i>=0;i--){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		d[i]=mx;
	}
	for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
	rep(i,H-1) chmax(ans,u[i]+d[i+1]);
	rep(i,H) rep(j,W) tmp[i][j]=x[i][j];
	rep(i,H) rep(j,W) x[j][i]=tmp[i][j];
	swap(H,W);
	rep(i,300) rep(j,300) tmp[i][j]=0;
	rep(i,300) u[i]=d[i]=0;
	rep(i,H){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		u[i]=mx;
	}
	rep(i,H-1) chmax(u[i+1],u[i]);
	rep(i,W) rep(j,W) tmp[i][j]=0;
	for(int i=H-1;i>=0;i--){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		d[i]=mx;
	}
	for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
	rep(i,H-1) chmax(ans,u[i]+d[i+1]);
	cout<<ans<<endl;
}

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
int N,L,t[100000],x[100000];
ll inf=1e18;
struct segtree{
	static const int p2=1<<17;
	int val[p2*2]={};
	ll at(int x){
		ll ret=0;
		x+=p2;
		while(x){
			ret+=val[x];
			x/=2;
		}
		return ret;
	}
	void add(int a,int b,int l,int r,int k,int v){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			val[k]+=v;
			return;
		}
		add(a,b,l,(l+r)/2,k*2,v);
		add(a,b,(l+r)/2,r,k*2+1,v);
	}
	void add(int a,int b,int v){
		add(a,b,0,p2,1,v);
	}
	int pos(){
		int ub=L+1,lb=-1;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(at(m)>=0) ub=m;
			else lb=m;
		}
		return ub;
	}
} seg;
int main(){
	cin>>N>>L;
	rep(i,N) cin>>t[i]>>x[i];
	int le=0;
	rep1(i,N){
		if(i==N||t[i-1]!=t[i]){
			reverse(x+le,x+i);
			le=i;
		}
	}
	ll sum=0;
	rep(i,N){
		sum+=x[i];
		int p=seg.pos();
		seg.add(0,x[i],-1);
		seg.add(x[i],p,1);
//		show(x[i]);
//		show(p);
	}
	rep(i,L+1) sum+=seg.at(i);
	cout<<sum<<endl;
}

実はC,D,Eの中ではEが一番短いという