kmjp's blog

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

AtCoder AGC #016 : E - Poor Turkeys

ゴリ押しで解けてしまった。
http://agc016.contest.atcoder.jp/tasks/agc016_e

問題

1~Nの番号のついた鳥がいる。
1~Mの番号の人が順に来て、以下の動作を行う。

  • 鳥X[i],Y[i]がともに残っている場合、どちらかを等確率で食べる。
  • 鳥X[i],Y[i]が片方だけ残っている場合、残っている方を食べる。
  • 鳥X[i],Y[i]がどちらも残っていない場合、何もしない。

鳥の対(i,j)のうち両方とも残っている可能性があるのは何組か。

解法

いくつか解法があるようだ。
基本的な考えは、鳥aが残っている場合の条件を考え、処理を巻き戻していくことである。
X[i]、Y[i]のいずれかに、以後残っていなければならない鳥がある場合、i番の人の時点では両方残っていなければならない。
こうして残っていなければならない鳥の範囲を伝搬させていく。
もし途中X[i]、Y[i]ともに以後残っていなければならない鳥である場合、最初に選んだaを残すことはできない。

O(N^2*M)解法

鳥の対(i,j)に対し、上記の手順で処理を巻き戻していき、i,jを最終的に残すために残さなければいけない鳥を求めていこう。
このままだとO(N^2*M)かかるが、関係ない鳥の処理はスキップするなどの枝刈りをすると通る。
自分もこれでムリヤリ通した。

O(N^3+NM)解法

個々の鳥ではなく、最初から鳥のペアが同時に残るかを見ていこう。
すなわち以下の値が最後までtrueになる組の数を考えていく。
f(x,y) := 鳥x,yがともに生き残っているかどうかの真偽値

今度は処理を巻き戻さず先頭から処理していく。

  • f(X[i],Y[i]) = Trueの場合
    • i番の人が訪れることで、X[i]、Y[i]の両方が残ることはありえなくなったので、f(X[i],Y[i])=Falseにする。
    • Warshall-Floyedの要領でこの状態を伝搬させていく。たとえばf(x,z)=falseなら、f(y,z)もfalseになる。これは生き残らなければいけない鳥の関係が閉路を形成してしまったことに相当する。
  • f(X[i],Y[i]) = Falseの場合
    • i番の人が訪れることで、X[i]、Y[i]は両方残らないことが確定した。よってf(X[i],z)=False、f(Y[i],z)=Falseとする。
int N,M;
int ok[404][404];
int A[101010],B[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) FOR(x,N) ok[y][x]=(y!=x);
	
	while(M--) {
		cin>>x>>y;
		x--;y--;
		if(ok[x][y]) {
			ok[x][y]=ok[y][x]=0;
			FOR(i,N) if(ok[x][i]==0) ok[y][i]=ok[i][y]=0;
			FOR(i,N) if(ok[y][i]==0) ok[x][i]=ok[i][x]=0;
		}
		else {
			FOR(j,N) ok[x][j]=ok[j][x]=ok[y][j]=ok[j][y]=0;
		}
	}
	
	int ret=0;
	FOR(y,N) FOR(x,y) ret+=ok[y][x];
	cout<<ret<<endl;

}

まとめ

最終的なコードは短いんだよな。