kmjp's blog

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

AtCoder AGC #047 : B - First Second

ARC

久しぶりにAGCで割とまともなパフォーマンスが出た。
https://atcoder.jp/contests/agc047/tasks/agc047_b

問題

異なるN個の文字列S[i]が与えられる。
文字列の対(S[i],S[j])において、どちらか片方に対し「先頭2文字のうち、片方を残し片方を削除する」という処理を繰り返して両者を一致させられるようなもの数を答えよ。

解法

先頭をいじるのは扱いにくいので、全文字列を反転させて末尾をいじることにしよう。
2つの文字列(U,V)に対し、|U|＜|V|であるとき、条件を満たすのは下記の場合である。

  • 両者先頭|U|-1文字が一致
  • Uの最後の文字と同じ文字が、|V|の|U|文字目以降に最低1個登場する。

これを愚直に求めて行こう。
EditorialではTrieを使ったが、ここでは自分が取った解法を紹介。効率は良くないけど。

まず前処理として、各文字を反転後ソートし、かつ隣接要素のLCPを求めておく。
さらにそれをダブリングし、文字列の配列の区間内におけるLCPを高速に求められるようにしていこう。

各文字について、1文字目、2文字目…と処理していくことを考える。
「～～最低1個登場する」を数え上げるため、BITを26個準備し、各文字列に対し、未処理の位置に各文字の登場の有無を0/1で格納して区間内のある文字の登場回数を高速に求められるようにしておく。

今、i文字目を処理することを考えよう。

  • S[x]がi文字より多いの場合
    • S[x]からi文字目を除いた場合を考え、BITを更新する。
  • S[x]がi文字の場合
    • S[x]とLCPが(i-1)文字以上一致する区間を、ダブリングした区間のLCPを用いて高速に求める。
    • その区間内で、BITを参照してS[x]の末尾と同じ文字を持つものを数え上げる。
string S[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,18> bt[26];

int same[202020][20];
int num[202020][26];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> cand;
	cin>>N;
	FOR(i,N) {
		cand.push_back(i);
		cin>>S[i];
		reverse(ALL(S[i]));
	}
	sort(S,S+N);
	
	FOR(i,N-1) {
		j=0;
		while(j<S[i].size()&&j<S[i+1].size()&&S[i][j]==S[i+1][j]) j++;
		same[i][0]=j;
	}
	FOR(i,N) {
		//cout<<i<<" "<<S[i]<<endl;
		FORR(c,S[i]) {
			c-='a';
			num[i][c]++;
		}
		FOR(j,26) if(num[i][j]) bt[j].add(i,1);
	}
	
	FOR(i,18) {
		FOR(j,N) {
			same[j][i+1]=min(same[j][i],same[min(N,j+(1<<i))][i]);
		}
	}
	
	ll ret=0;
	for(i=1;i<=1010000;i++) {
		vector<int> cand2;
		FORR(c,cand) {
		//	cout<<i<<c<<endl;
			if(S[c].size()==i) {
				char tc=S[c].back();
				bt[tc].add(c,-1);
				
				x=c;
				y=c;
				for(j=18;j>=0;j--) {
					if(same[x][j]>=i-1) x+=1<<j;
					if(x>=N) x=N;
					if(y-(1<<j)>=0 && same[y-(1<<j)][j]>=i-1) y-=1<<j;
				}
				ret+=bt[tc](x)-bt[tc](y-1);
				//cout<<"!"<<c<<" "<<x<<" "<<y<<" "<<bt[tc](x+1)-bt[tc](y-1)<<endl;
			}
			else {
				cand2.push_back(c);
			}
		}
		FORR(c,cand2) {
			char tc=S[c][i-1];
			num[c][tc]--;
			if(num[c][tc]==0) bt[tc].add(c,-1);
		}
		swap(cand,cand2);
	}
	
	cout<<ret<<endl;
	
}

まとめ

AGCの記事最近あんまり書いてないな。