競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

CodeChef April long Challenge 2015 Black-white Board Game(BWGAME)

注:この記事はCodeChef終了後に更新しています。
本番中解けませんでした。
自分なりに理解して実装してみたのですが計算量が怪しいです。

- 問題概要

N*Nマスのボードがあります。
i行について、L_iからR_iまでのマスが黒色に塗りつぶされています。
黒じゃないマスは白色に塗りつぶされています。
1,,,Nの値で構成される順列をP[1,,,N]とします。
x行y列目のマスをb(i,j)と表すことにします。
A君は(i,P[i])が全て黒色のマスとなる順列Pのうち偶順列のものを見つけます。
F君は(i,P[i])が全て黒色のマスとなる順列Pのうち奇順列のものを見つけます。
A君とF君は頭がいいので該当する順列を全て見つけることができます。
ボードが与えられたとき、どちらが多く順列を見つけられるか答えなさい。

- 解法

順列を全て列挙すれば13点がもらえます。

Nが大きいときの解法について考えていきます。
行列式の性質に着目しましょう。
行列式の定義として、Pが偶順列となるb(i,P[i])の積の総和をEとし、Pが奇順列となるb(i,P[i])の積の総和をOとするとE-Oとなります。
このへんは行列式の定義を詳しく解説しているところが他にあると思うのでそちらを参照してください。
積ということは、b(i,j)が黒マスのところを1,b(i,j)が白マスのところを0とすると、Eは偶順列となり全て黒マスの順列の組み合わせ数、Oは奇順列となり全て黒マスの順列の組み合わせ数となります。
E,Oは直接求めることはできませんがE-Oが分かるのでどちらが多いか計算で求まります。
通常の行列式ならばO(N^3)で求められるアルゴリズムが存在するので二つ目の部分点もゲットです。

上記で行列式を求めることで解が得られるのがわかりました。
もっと効率的に行列式を求める方法について考えます。
黒マスになっているマスは横に連続になっていることを使います。
そもそもN=10^5ではボードの二次元配列すら用意することができません。
行列式を求めるには三角行列を作ります。
ここでは下三角行列を作ります。
まずLの値ごとに(L,R)をまとめます。
(1,1),(2,3),(1,2)(1,4)なら行列式に直すと以下の形になり、
1000
0110
1100
1111
これを以下のように変形します
1000
1100
1111
0110
行の交換には符号の反転が必要ですがあとで求められるので今は無視です。
ここから三角行列を作りたいので、まず1列目の1がある行が3つあるので
最もRの小さい一番上の行を引きます。
1000
0100
0111
0110
1行目が確定しました。
2行目移行について考えます。同じようにRの小さいものを採用し、それを他のものから引きます。
1000
0100
0011
0010
3行目も同様にRの小さいものを採用します。
1000
0100
0010
0001
下三角行列というか単位行列ができました。
ここで、Rの小さいものから採用していくという手法をとると行列式には0と1しか現れません。
これに正負がつくので行列式の解、すなわち偶順列と奇順列の差は最大で1ということもわかります。
最後に正負の判定ですが、できた三角行列の各行がもともとどの行にあったかを調べます。
1000(1)
0100(3)
0010(2)
0001(4)
この1,3,2,4という順列が奇順列なら-,偶順列なら+になります。
あとはこの作業をどう実装するかなのですが同じLのグループの中からRの最小値を一つ取り出せればよいのでヒープを使いました。
ヒープをN個用意し、要素を一つ取り出すとそのヒープをR+1のヒープにマージさせます。
マージの処理が重いのでR+1のヒープが空の時は参照を移すだけにすれば軽くなります。
Nが大きいときのテストケースが甘いみたいで、こんな感じの雑解法でもACもらえました。
順列の転倒数はBITを使えば簡単に得られます。

- ソースコード

Nが小さいときのテストケースが多く、13点の部分でTLEを起こしてしまったのでNが小さいときは順列全列挙に切り替えるように組んでいます。

#include<stdio.h>
#include<map>
#include<queue>
#include<functional>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;


typedef pair<int,int> P;
int A,F;
int inv=0;
void pe(int d,int dm,int* p,int b[10][10]){
	if(d==dm){
		int cnt=0;
		for(int i=0;i<dm;i++)
			for(int j=i+1;j<dm;j++)
				if(p[i]>p[j])cnt++;
		if(cnt&1)F++;
		else A++;
	}
	for(int i=d;i<dm;i++){
		swap(p[d],p[i]);
		if (p[d] > p[i])inv++;
		if (b[d][p[d]])pe(d + 1, dm,p,b);
		if (p[d] > p[i])inv--;
		swap(p[d], p[i]);
	}
}

inline int smallsolve(int N){
	int L,R;
	A=F=0;
	int board[10][10]={{0}};
	int p[10];
	for(int i=0;i<N;i++){
		scanf("%d %d",&L,&R);
		for(int j=L-1;j<R;j++)
			board[i][j]=1;
		p[i]=i;
	}
	pe(0,N,p,board);

	return (A-F);
}

inline int sum(int i,vector<int> &bit){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=i&(-i);
	}
	return s;
}

inline void add(int i,int x,vector<int> &bit,int n){
	while(i<=n){
		bit[i]+=x;
		i+=i&(-i);
	}
}

char ans[3][10]={"Fedor","Draw","Alex"};


inline int bigsolve(int N){
	int L,R,res=0;
	vector<list<P> >input(N);
	vector<priority_queue<P,vector<P>,greater<P>>>que(N);
	vector<int> par(N+1);
	vector<int> p(N);

	for(int i=0;i<N;i++){
		scanf("%d %d",&L,&R);
		input[--L].push_back(make_pair(--R,i+1));
		par[i]=i;
	}
	bool z=false;
	for(int i=0;i<N;i++){
		for(auto &l:input[i])que[par[i]].push(l);
		if(que[par[i]].empty()||que[par[i]].top().first<i){
			z=true;break;
		}
		P t=que[par[i]].top();//printf("%d,%d\n",t.first,que[par[i]].size());
		que[par[i]].pop();
		p[i]=t.second;
		if(par[t.first+1]==t.first+1)
			par[t.first+1]=par[i];
		else
		{
			if(que[par[t.first+1]].size()>que[par[i]].size()){
				while(!que[par[i]].empty()){
					que[par[t.first+1]].push(que[par[i]].top());
					que[par[i]].pop();
				}
			}
			else{
				while(!que[par[t.first+1]].empty()){
					que[par[i]].push(que[par[t.first+1]].top());
					que[par[t.first+1]].pop();
				}
				par[t.first+1]=par[i];
			}

		}
	}


	if(!z){
		vector<int> bit(N+1,0);
		int s=0;
		for(int i=0;i<N;i++){
			s+=i-sum(p[i],bit);
			add(p[i],1,bit,N);
		}
		if(s&1)res=-1;
		else res=1;
	}
	return res;
}


int main(void){
	int T;
	scanf("%d",&T);

	while(T--){
		int N,res=0;
		scanf("%d",&N);
		if(N>=8)
			res=bigsolve(N);
		else
			res=smallsolve(N);


		puts(ans[1+res]);
	}

}