結果

問題 No.2893 Minahoshi (Hard)
コンテスト
ユーザー kotatsugame
提出日時 2024-09-13 23:23:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,988 bytes
コンパイル時間 1,755 ms
コンパイル使用メモリ 101,928 KB
実行使用メモリ 27,532 KB
最終ジャッジ日時 2024-09-13 23:23:42
合計ジャッジ時間 11,387 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 2 WA * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cassert>
#include<atcoder/string>
using namespace std;
int A(int n)
{
	int j=0;
	while((1<<j+1)+j<n)j++;
	return j;
}
long f(string S)
{
	vector<int>sa=atcoder::suffix_array(S);
	vector<int>lcp=atcoder::lcp_array(S,sa);
	long ret=0;
	for(int l:lcp)ret+=l;
	return ret;
}
vector<vector<int> >G;
string V;
void dfs(int u)
{
	while(!G[u].empty())
	{
		int v=G[u].back();
		G[u].pop_back();
		dfs(v);
		//u->v
		V+='a'+(v&1);
	}
}
string mk(int n)
{
	int a=A(n);
	G.assign(1<<a,vector<int>());
	for(int i=0;i<1<<a;i++)
	{
		for(int j=0;j<2;j++)
		{
			int v=i<<1|j;
			v&=(1<<a)-1;
			if(i!=v)G[i].push_back(v);
		}
	}
	int cnt=a+(1<<a)*2-2;
	assert(cnt>=n-2);
	if(cnt==n-2)cnt++,G[0].push_back(0);
	if(cnt==n-1)cnt++,G[(1<<a)-1].push_back((1<<a)-1);
	V.clear();
	dfs(0);
	for(int i=0;i<1<<a;i++)assert(G[i].empty());
	V+=string(a,'a');
	reverse(V.begin(),V.end());
	assert(V.size()>=n);
	//for(int i=0;i+n<=V.size();i++)cout<<i<<" "<<f(V.substr(i,n))<<"\n";
	string ret=V.substr(0,n);
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int N=2;N<=0;N++)
	{
		long mn=1e9;
		vector<string>can;
		for(int i=0;i<1<<N;i++)
		{
			string S="";
			for(int j=0;j<N;j++)S+=i>>N-j-1&1?'b':'a';
			long t=f(S);
			if(mn>t)mn=t,can.clear();
			if(mn==t)can.push_back(S);
		}
		cout<<"N = "<<N<<" : mn = "<<mn<<endl;
		/*
		vector<int>AA,BB;
		for(string S:can)if(S[0]=='a')
		{
			vector<int>R;
			for(int i=0;i<N;)
			{
				int j=i+1;
				while(j<N&&S[i]==S[j])j++;
				R.push_back(j-i);
				i=j;
			}
			if(R[0]!=A(N)+1)continue;
			vector<int>A,B;
			for(int i=0;i<R.size();i++)(i%2==0?A:B).push_back(R[i]);
			AA=A,BB=B;
		}
		{
			cout<<"[";for(int a:AA)cout<<a<<",";cout<<"]";
			cout<<" ";
			cout<<"[";for(int a:BB)cout<<a<<",";cout<<"]";
			cout<<endl;
		}
		*/
		string S=mk(N);
		cout<<S<<" "<<f(S)<<endl;
	}
	int T;cin>>T;
	for(;T--;)
	{
		int N;cin>>N;
		cout<<mk(N)<<"\n";
	}
}
0