Codeforces Global Round 11 : F. Boring Card Game

これはわからず。
https://codeforces.com/contest/1427/problem/F

問題

1～6Nのカードが順に並んでいる。
ここで、2人で交互にNターンずつ以下を行う。

• 連続するカードを3枚取り除く。その後、残ったカードは間を詰める。

最終的に両者が得られたカードの一覧が得られるとき、取り除く順番を求めよ。

解法

証明はEditorialを見てもらうとして、以下は解き方だけ紹介。
先手は貪欲にとれるところを取っていってよい。
後手は、極力先手の手を妨げない、すなわち「これを取らないと、その外側にある3枚が取れない」という箇所を優先的にとればよい。

int N;
int pat[2020];
vector<vector<int>> cand[2];
int root[2020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=6*N;i++) {
		pat[i]=root[i]=1;
		bt.add(i,1);
	}
	FOR(i,3*N) {
		cin>>x;
		pat[x]=0;
	}
	
	vector<int> V;
	for(i=1;i<=6*N;i++) {
		if(V.size()>=2 && pat[V[V.size()-2]]==pat[i]&&pat[V[V.size()-1]]==pat[i]) {
			for(x=V[V.size()-2]+1;x<i;x++) root[x]=0;
			cand[pat[i]].push_back({V[V.size()-2],V[V.size()-1],i});
			V.pop_back();
			V.pop_back();
			
		}
		else {
			V.push_back(i);
		}
	}
	assert(V.empty());
	
	vector<vector<int>> R;
	FOR(i,N) {
		FOR(x,2) {
			y=0;
			FORR(c,cand[x]) {
				if(bt(c[0])-bt(c[0]-1)==0) continue;
				if(bt(c[1])-bt(c[1]-1)==0) continue;
				if(bt(c[2])-bt(c[2]-1)==0) continue;
				if(bt(c[2])-bt(c[0]-1)!=3) continue;
				if(x==1&&root[c[0]]) continue;
				R.push_back(c);
				bt.add(c[0],-1);
				bt.add(c[1],-1);
				bt.add(c[2],-1);
				y=1;
				break;
			}
			if(y==0) {
				FORR(c,cand[x]) {
					if(bt(c[0])-bt(c[0]-1)==0) continue;
					if(bt(c[1])-bt(c[1]-1)==0) continue;
					if(bt(c[2])-bt(c[2]-1)==0) continue;
					if(bt(c[1])-bt(c[0])!=1) continue;
					if(bt(c[2])-bt(c[0]-1)!=3) continue;
					R.push_back(c);
					bt.add(c[0],-1);
					bt.add(c[1],-1);
					bt.add(c[2],-1);
					break;
				}
			}
		}
	}
	
	FORR(r,R) cout<<r[0]<<" "<<r[1]<<" "<<r[2]<<endl;
	
	
}

まとめ

本番中これを確信持って通すのは難しいよなぁ。