問題文を読み間違えた…。
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よりコードが短い。