AtCoder ABC #266 : Ex - Snuke Panic (2D)

そのライブラリは持ってなかった。
https://atcoder.jp/contests/abc266/tasks/abc266_h

問題

2次元座標上原点にキャラがいる。このキャラは

• X軸と平行に単位時間あたり1以下速さで左右移動する
• Y軸と平行に単位時間あたり1以下速さで上に移動する
• 移動しない

のいずれかを行うことができる。

時刻T[i]に座標(X[i],Y[i])にいるとポイントA[i]を得られる、という条件が複数与えられる。
最適な移動経路を取るとき、合計ポイントの最大値を求めよ。

解法

a番の条件ののちb番の条件を満たすには

• Y[a]≦Y[b]
• |X[a]-X[b]|+Y[b]-Y[a]≦T[b]-T[a]

の両方を満たせばよい。

後者の条件は、以下の両方を満たせばよいことと同値である。

• T[a]+X[a]-Y[a]≦T[b]+X[b]-Y[b]
• T[a]-X[a]-Y[a]≦T[b]-X[b]-Y[b]

そこで、P[i]=T[i]+X[i]-Y[i]、Q[i]=T[i]-X[i]-Y[i]と座標変換する。

そうすると、以下の3つの条件をすべて満たせればよいことになる。

• Y[a]≦Y[b]
• P[a]≦P[b]
• Q[a]≦Q[b]

条件をY[i]昇順で見ていくことを考える。
最後にポイントを得た変換後の座標(p,q)に対し、そこまでの総ポイントの最大値を2次元配列に置くことを考える。

2次元BITや2次元SegTreeで、(0,0)-(p,q)の範囲内の最大値を求められると、今見ているi番の条件を満たす場合の合計ポイントの最大値を求めることができる。
2次元BITは、値の管理にmapを使う1次元BITを、これまたBITの要領で配置することで、メモリ使用量も押さえて実現できる。

template<class V, int ME> class BIT_map {
public:
	unordered_map<ll,V> bit;
	V op(V a,V b){ return max(a,b); };
	//V op(V a,V b){ return a+b };
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s=op(s,bit[e-1]),e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]=op(bit[e-1],v),e+=e&-e;}
};

template<class BIT,class V,int ME> class BIT_2D {
public:
	vector<BIT> bit;
	BIT_2D(): bit(1<<ME){};
	V op(V a,V b){ return bit[0].op(a,b); };
	V operator()(int e,int b) {if(e<0) return 0;V s=0;e++;while(e) s=op(s,bit[e-1](b)),e-=e&-e; return s;}
	void add(int e,int b,V v) { e++; while(e<=1<<ME) bit[e-1].add(b,v),e+=e&-e;}
};
BIT_2D<BIT_map<ll,18>,ll,18> bit;

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<vector<ll>> V;
	vector<ll> Xs,Ys;
	Xs.push_back(0);
	Ys.push_back(0);
	
	cin>>N;
	FOR(i,N) {
		ll t,x,y,a;
		cin>>t>>x>>y>>a;
		if(t-x-y>=0&&t+x-y>=0) {
			V.push_back({y,t-x-y,t+x-y,a});
			Xs.push_back(t-x-y);
			Ys.push_back(t+x-y);
		}
	}
	sort(ALL(V));
	sort(ALL(Xs));
	sort(ALL(Ys));
	
	ll ma=0;
	FORR(v,V) {
		ll x=lower_bound(ALL(Xs),v[1])-Xs.begin();
		ll y=lower_bound(ALL(Ys),v[2])-Ys.begin();
		ll r=bit(x,y)+v[3];
		ma=max(ma,r);
		bit.add(x,y,r);
	}
	cout<<ma<<endl;
		
	
	
}

まとめ

そもそもmapを使う1次元BITも組んだことなかったし、それを活かした2次元BITも初めて組んだ。