kmjp's blog

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

天下一プログラマーコンテスト2018 : F - Circular

本番は時間切れ。
https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_f

問題

1~NのpermutationであるPがあったとする。
PをQ[i]=min(P_[(i-1)%N],P[i])で構成されるQに置き換えるという処理を任意回数行ったとする。

処理後の数列Aが与えられたとき、元のPの組み合わせ数を求めよ。

解法

Aでは同じ数字は連続してなければいけない。
そこで、Aの先頭に1が集まるようrotateしておくとラクである。

処理回数をXとすると、XはA中1の連続する数-1であることが確定する。
よって以下のケースでは明らかに不適合。

  • Aに同じ数字の登場位置が不連続
  • 同じ数字が(X+1)よりも多く並ぶ。

これを踏まえて、小さい順に配置可能な位置を求めかけ合わせていこう。
今P中で数iを置くことを考える。

  • iの登場位置の前後のうち少なくとも片方がiより大きい
    • 処理を繰り返す過程でiがより大きな数字を塗りつぶさないために、iの初期位置は一意に確定する。そこでその位置は要素指定済みとみなす。
  • iの登場位置の前後のうち少なくとも片方がiより小さい
    • 登場数がYのとき、iの初期位置はX-Y+1通り考えられるので、解に(X-Y+1)を掛ける
  • iがP中登場しない
    • すでに自身より小さい数字で塗りつぶされた領域のうち、そこから(X+1)個連続して塗りつぶされているような箇所があれば、それらが解の候補になる。そのうちすでに塗りつぶされた数を減らした回の分だけ解に掛ける。
    • なお、上記2パターンでは「すでに自身より小さい数字で塗りつぶされた領域のうち、そこから(X+1)個連続して塗りつぶされているような箇所」を更新しておこう。
ll mo=998244353;
int N;
int B[1303030];
int A[1303030];

vector<int> P[303030];
int L[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
	}
	
	if(count(A,A+N,0)==0) return _P("0\n");
	if(count(A,A+N,0)==N) {
		ll ret=1;
		FOR(i,N) ret=ret*(i+1)%mo;
		cout<<ret<<endl;
		return;
	}
	
	FOR(i,N) if(A[i]==0 && A[(i+N-1)%N]>0) {
		FOR(j,2*N) B[j]=A[(i+j)%N];
		FOR(j,2*N) A[j]=B[j];
		FOR(j,N) P[A[j]].push_back(j);
		break;
	}
	
	ll ret=1;
	set<int> empty,unused;
	int numfree=0;
	
	empty.insert(4*N);
	FOR(i,N) empty.insert(i), empty.insert(i+N);
	
	FOR(i,N) {
		L[i]=P[i].size();
		if(L[i]>L[0]) return _P("0\n");
		if(L[i]==0) {
			ret=ret*numfree%mo;
			numfree--;
		}
		else {
			if(P[i][0]+L[i]-1!=P[i].back()) return _P("0\n");
			FORR(p,P[i]) {
				empty.erase(p);
				empty.erase(N+p);
				unused.insert(p);
			}
			
			x=P[i][0];
			if(A[x+N-1]>i && A[x+L[i]]>i && L[i]!=L[0]) return _P("0\n");
			if(A[x+N-1]<i && A[x+L[i]]<i) ret=ret*(L[0]-L[i]+1)%mo;
			auto it=unused.lower_bound(P[i][0]-(L[0]-1));
			while(it!=unused.end() && *it<=P[i].back()) {
				auto it2=empty.lower_bound(*it);
				if(*it2-*it<L[0]) {
					it=unused.lower_bound(*it2);
				}
				else {
					numfree++;
					it=unused.erase(it);
				}
			}
			numfree--;
		}
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

自力で最後まで詰められたか微妙。