kmjp's blog

競技プログラミング参加記です

JOIG 2024/2025 本選 : E - 神経衰弱 2 (Pair Matching 2)

問題文を読み間違えた…。
https://atcoder.jp/contests/joig2025-open/tasks/joig2025_e

問題

1~Nの整数が書かれたカードが2枚ずつ、計2N枚ある。
また、カードの番号iに応じて得点が割り当てられている。

カードの並びが与えられるので、プレイヤーは以下の行動のいずれかを取る。

  • 無視する
  • カードを拾う
    • もしすでに、拾うカードと同じ整数のカードを持っている場合、両者を捨てて番号に応じた得点を得る
    • 左手にカードがあれば、を捨てる
    • 右手にカードがあれば、左手に移す
    • 拾うカードを、まだ捨ててなければ右手に移す

最終的に得られるカードの総得点の最大値を求めよ。

解法

得点につながらないカードはそもそも拾う必要がない。
その場合、拾い方は過去の2パターンの繰り返しとなる。

  • 1種類のカードを2枚連続で拾う。
  • 2種類のカードを交互にA→B→A→Bのように拾う。

区間最大値を取れるSegTreeを用いながら、順にカードを拾う場合をシミュレートしていく。
後者でいう2回目のAを拾ったタイミングで、もし今後2回目のBを拾う場合、1回目のAの手前までの得点とAをそろえることによる得点を得られるようにSegTreeを更新していこう。

int N;
int A[808080];
int V[404040];
int pre[808080];

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]);
	}
};
SegTree_1<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>A[i];
		pre[i]=-1;
	}
	FOR(i,N) cin>>V[i];
	
	ll ma=0;
	FOR(i,2*N) {
		x=A[i]-1;
		if(pre[x]==-1) {
			pre[x]=i;
		}
		else {
			//1212のケース。1*1の部分はpre[x]の手前に計算済み
			ma=max(ma,st.getval(0,pre[x])+V[x]);
			// 11のケース
			st.update(pre[x],st.getval(pre[x],pre[x]+1)+V[x]);
		}
		st.update(i,ma);
		
	}
	cout<<ma<<endl;
}

まとめ

結果的にDよりコードが短い。