M-SOLUTIONS プロコンオープン : F - Random Tournament

いやこれは解けるべきだったな…。
https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_f

問題

N人の人がおり、互いに1vs1で対戦するとどちらが勝利するかという情報が与えられる。
このN人が横1列に順に並んでいる。

隣接する2人を選んで対戦させ、負けた方を列から取り除き隙間を詰める、という作業を繰り返す。
対戦順によって最後の1人になりうるのはN人中何人か。

解法

先日のSRMで激しく既視感がある。
TopCoder SRM 759: Div1 Hard EllysTournament - kmjp's blog

実際、上記問題では状態に対し確率を持たなければいけなかったが、こちらは勝利しうるかどうかの2値だけ持てばよい。
よって上の問題と同じ状態遷移をbitset使って高速化すればO(N^3)で通る。
bitsetのbit演算で複数条件のandの有無を判定できるよう、値の並び順に気を付けよう。

Editorialの解法とは微妙に状態遷移が違うね。

int N;
bitset<2020> A[2020];
bitset<2020> winL[2020],winR[2020],winRL[2020],winRR[2020];
bitset<2020> dp[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(j=1;j<N;j++) {
		cin>>s;
		FOR(i,j) {
			A[j][i]=s[i]=='1';
			A[i][j]=s[i]=='0';
		}
	}
	
	FOR(x,N) winL[x][x]=winR[x][x]=winRL[x][x]=winRR[x][x]=1;
	for(l=2;l<=N;l++) {
		for(x=0;x+l<=N;x++) {
			y=x+l-1;
			auto bs=winL[x] & (winR[y]>>1);
			if(bs.count()) dp[x][y]=dp[y][x]=1;
			bs=A[x] & dp[x] & winRL[y];
			if(bs.count()) winL[x][y]=winRL[y][x]=1;
			bs=A[y] & dp[y] & winRR[x];
			if(bs.count()) winR[y][x]=winRR[x][y]=1;
		}
	}
	int ret=0;
	FOR(i,N) ret+=winR[i][0]&winL[i][N-1];
	
	cout<<ret<<endl;
	
}

まとめ

O(N^3)は思いついて、そこからうまく状態の持ち方を工夫してbitsetに持ち込めばよかったのだが、無理にO(N^2)解を探しに行ったのが敗因。