結果

問題 No.2454 Former < Latter
コンテスト
ユーザー planes
提出日時 2023-09-01 22:23:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 2,304 bytes
コンパイル時間 1,701 ms
コンパイル使用メモリ 163,052 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-03 09:27:26
合計ジャッジ時間 2,774 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

  #include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

ll INF=2e18;
vector<int> Z_algorithm(string S) {
	int c = 0, n = S.size();
	//接頭辞の長さを保存する配列を返す。
	//i = 1からやるとする。
	//Z[1]には赤下線が存在しないので、「溢れるor共通部分がない」のところにまずいく。
	//実装上、上のような挙動をしてもらうため、Z[0]=n;は[1, n - 1]まで計算が終わった後に入れる。
	//cは、赤下線の左端の位置。
	vector<int> Z(n, 0);
	for (int i = 1; i < n; i++) {
		int l = i - c;
		//今着目してる部分が赤下線の左端から何個分離れているかをlに入れる。
		if (i + Z[l] < c + Z[c]) {
			//この条件を満たすのは、「青下線が赤下線に収まる」。
			//この時、すでに計算されてるなのでそれを流用する。
			Z[i] = Z[l];
		}
		else {
			//この条件を満たすのは、「赤下線から青下線が溢れる」or「赤下線と青下線の共通部分がない」。
			int j = max(0, c + Z[c] - i);
			//c + Z[c] - i > 0の時、これは「溢れる」が該当する。
			//溢れてるのなら、収まる分は計算せずに、溢れた分(j番目から)だけ愚直に突き合わせればよい。
			//そもそも共通部分がないならば、全部突き合わせる。この時、式からj = 0;となるとわかる。

			//愚直に突き合せてる部分
			while (i + j < n && S[j] == S[i + j])j++;
			
			Z[i] = j;
			//今の見てるiで、赤下線に完全に含まれなくなったので、今のiを赤下線の左端として、次のiをまた計算する。
			c = i;
		}
	}

	//最後にこれを忘れずに
	Z[0] = n;
	return Z;
}


void solve() {
ll N;cin>>N;
string S;cin>>S;
auto vec=Z_algorithm(S);
ll ans=0;

for(ll i=1;i<N;i++) {
  ll f=i;
  ll b=N-i;

  if(vec[i]<f&&vec[i]<b) {
    if(S[vec[i]]<S[i+vec[i]]) ans++;
  }
  
  else if(vec[i]<b) {
    if(vec[i]>=f) ans++;
  }
  
  else {
    if(vec[i]>f) ans++;
  }
  
}

cout<<ans<<endl;


}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll t;cin>>t;
  for(ll i=0;i<t;i++) {
    solve();
  }

}
0