yukicoder : No.1951 消えたAGCT(2)

意外にも愚直でいいのか。
https://yukicoder.me/problems/no/1951

問題

文字列Sが与えられる。
Sに以下の処理をS中に'A''T''G''C'が1個もなくなるまで繰り返し適用するとする。
処理を何回行う必要があるか。

• S中の'A''T''G''C'の個数をC1とする。
• SのC1文字目を削除した文字列をTとする。
• 削除した文字と同じ文字の、T中における個数をC2とする。
• Tの各文字をC2だけローテートする。
• SにTを代入する。

解法

BITを持ち、最初の文字列のうち、各位置の文字がまだ残っているかどうかを0/1で管理しよう。
加えて26個BITを持ち、上記BITを各アルファベットの文字ごとに分解したものを持とう。

C1のカウントは、後者のBITで容易に計算できる。
また、SのC1文字目は、前者のBITを二分探索して計算できる。
C2のカウントも、後者のBITで容易に計算できる。

int N;
string S;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[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) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> C[26],sum;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		S[i]-='A';
		sum.add(i,1);
		C[S[i]].add(i,1);
	}
	
	int ret=0;
	int rot=0;
	while(1) {
		x=C[(26-rot)%26](N)+C[(26-rot+2)%26](N)+C[(26-rot+'G'-'A')%26](N)+C[(26-rot+'T'-'A')%26](N);
		if(x==0) break;
		ret++;
		y=sum.lower_bound(x);
		sum.add(y,-1);
		C[S[y]].add(y,-1);
		rot+=C[S[y]](N);
		rot%=26;
	}
	cout<<ret<<endl;
}

まとめ

最近AGC少ないね。