kmjp's blog

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

AtCoder ARC #025 : D - コンセント

ARC

うーん、これは本番では最後まで行けないな…。
http://arc025.contest.atcoder.jp/tasks/arc025_4

問題

H*W個の穴が並んでいる。
このうち、隣接する２穴を占有して１つのコンセントプラグを差すことができる。

ここで、以下のN個のクエリに処理せよ。

  • 穴の位置(S[i],T[i])が与えられるので、そこの穴を塞ぐまたは既に塞いでいたら穴を空ける。
  • その都度、コンセントプラグの差し方の組み合わせを答えよ。

解法

まず基本的なアイデアとして、左端の列からDPで解くことを考える。
DPの状態として、[処理中の列][次の列のうち使用済みの穴のbitmask]を持つ。
後者がわかりにくいが、今見ている列と次の列にまたがるようにプラグを差す場合、次の行はその列を（すでに他のプラグが差さっているので）利用できない。

クエリによって穴が塞がると、そこにさらにプラグを差すことはできない。
この条件でDPを行うと、O(H*W*2^(2H))で１回のクエリを処理できる。
部分点10点は上記DPをN回行い、O(N*H*W*2^(2H))で解けば間に合う。

満点解法ではWが大きく、これでは間に合わない。
ここで、このDPは直前の列におけるコンセントの差し方から算出できることから、行列表記すれば行列の累乗計算を行うことで長大な列におけるDP処理の計算量を落とすことができる。

まず、以下のようにクエリが生じる可能性がある列とそれ以外の列により、全部の列を分割しよう。
例えばクエリ中以下の位置が塞がる可能性がある場合：

...*......*..
......*...*..

クエリが生じる場所は１列分のみ、それ以外は一塊となるように分割する。

AAABCCDEEEFGG
...*......*..
......*...*..

列の塞がり具合のbitmaskをxとし、対応するDPの行列表記をP(x)とすると、上記状態は P(0)^3 \times P(1) \times P(0)^2 \times P(3) \times P(0)^2のように表記できる。
後は各項を ( (P(0)^3 \times P(1) ) \times (P(0)^2 \times P(3) ) ) \times P(0)^2のように２個ずつ組み合わせてSegTreeの要領で掛け算していく。

各クエリで特定位置のbitmaskが変更されたら、こちらもSegTreeの更新の要領で全体の行列の積を更新していけばよい。
塊の数は最大2N+1なので、SegTreeの深さはlog(2N+1)。
よって各クエリの計算量は行列の乗算に2^(6H)かかることを踏まえてO(logN*2^H)。
Nクエリ処理でO(N*logN*2^H)かかっても何とか間に合う。

ll H,W;
int N;
ll S[20050],T[20050];
int mask[100001];

ll mo=1000000007;
map<ll,int> XM;
vector<ll> XM2;

const int MAT=4;
struct Mat { ll v[MAT][MAT]; };
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	int i,x,y,z;
	Mat r;
	FOR(x,n) FOR(y,n) {
		r.v[x][y]=0;
		FOR(z,n) r.v[x][y] += (a.v[x][z]*b.v[z][y]) % mo;
		r.v[x][y] %= mo;
	}
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y,z;
	Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

const int NV=1<<17;
Mat val[NV*2];


Mat getmat(int h,int mask) {
	int x,y;
	Mat r;
	FOR(x,4) FOR(y,4) r.v[x][y]=0;
	r.v[0][0]=1;
	if(h==1) {
		if(mask==0) r.v[0][1]=r.v[1][0]=1;
	}
	else {
		if(mask==0) {
			r.v[0][0]=2;
			r.v[3][0]=1;
			r.v[2][1]=1;
			r.v[1][2]=1;
			r.v[0][3]=1;
		}
		if(mask==1 || mask==0) r.v[2][0]=r.v[0][2]=1;
		if(mask==2 || mask==0) r.v[1][0]=r.v[0][1]=1;
	}
	return r;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>S[i]>>T[i];
		S[i]--,T[i]--;
		XM[T[i]]=XM[T[i]+1]=0;
	}
	XM[0]=XM[W]=0;
	ITR(it,XM) it->second=XM2.size(), XM2.push_back(it->first);
	FOR(i,NV) val[i+NV].v[0][0]=1;
	
	Mat b=getmat(H,0);
	FOR(i,XM.size()-1) val[i+NV] = powmat(XM2[i+1]-XM2[i],b);
	for(i=NV-1;i>=1;i--) val[i]=mulmat(val[i*2],val[i*2+1]);
	
	FOR(i,N) {
		x=XM[T[i]];
		mask[x]^=1<<S[i];
		val[x+NV]=getmat(H,mask[x]);
		x+=NV;
		while(x>1) x>>=1, val[x]=mulmat(val[x*2],val[x*2+1]);
		
		cout << val[1].v[0][0] << endl;
	}
}

まとめ

行列のSegTreeは思い浮かばなかった。