yukicoder : No.873 バイナリ、ヤバいなり！ｗ

なんとか1時間切れて良かった。
https://yukicoder.me/problems/no/873

問題

01列とは、01が交互に現れる文字列である。
01で構成される文字列Sのスコアは、同じ文字が続く場合にその間に切れ目を入れ文字列を複数の01文字列に分割した場合、各01文字列長の二乗和とする。

整数Nが与えられる。
スコアがNとなる文字列のうち、最短の物を求めよ。
最短の物が複数ある場合、辞書順最小のものを求めよ。

解法

自分は、総長が最小となる01文字列長の組み合わせの候補を列挙し、それぞれに対し文字列を構成して最小のものを選んだ。
前者については、あるスコアを達成する最短の文字列長を一旦DPで求めておき、それを元に01文字列長を適当に探索すればよい。

さて、01文字列長の集合が与えられたとき、その中で辞書順最小の題意を満たす文字列を構成しよう。
先頭から見て、次に来る文字列の先頭が0の場合と1の場合で分岐する。

• 先頭が0の場合
  • 奇数長の01列が来ると、その次にもまた0が来るのでよい。短い奇数長の01列をできるだけ前に持って来よう。
  • 奇数長の01列が使えない場合、長い順に01列を使おう。
• 先頭が1の場合
  • 同様に、短い偶数列・長い偶数列・長い奇数列・短い奇数列の順で使うのが好ましい。

vector<int> W;
string ret;
int N;

int len[303030];

string hoge() {
	string S;
	multiset<int> V;
	FORR(v,W) V.insert(v);
	int i;
	int nex=0;
	while(V.size()) {
		if(nex==0) {
			FORR(v,V) {
				if(v%2==1) {
					FOR(i,v) S+=(char)('0'+(i%2));
					V.erase(V.find(v));
					goto out;
				}
			}
			auto v=*V.rbegin();
			V.erase(V.find(v));
			FOR(i,v) S+=(char)('0'+(i%2));
			nex=1;
		}
		else {
			int odd=0;
			FORR(v,V) {
				if(v%2==0) {
					FOR(i,v) S+=(char)('1'-(i%2));
					V.erase(V.find(v));
					nex=0;
					goto out;
				}
			}
			auto v=*V.rbegin();
			V.erase(V.find(v));
			FOR(i,v) S+=(char)('1'-(i%2));
			nex=1;
		}
		
		out:;
	}
	return S;
}


void dfs(int cur,int v) {
	if(cur==N) {
		ret=min(ret,hoge());
		return;
	}
	if(cur+v*v>N) return;
	if(cur+v*v<=N && len[cur]+v+len[N-(cur+v*v)]==len[N]) {
		W.push_back(v);
		dfs(cur+v*v,v);
		W.pop_back();
	}
	dfs(cur,v+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N+1) len[i]=i;
	
	for(i=1;i<=600;i++) for(j=0;j+i*i<=N;j++) len[j+i*i]=min(len[j+i*i],len[j]+i);
	
	ret="z";
	dfs(0,1);
	
	cout<<ret<<endl;
	
}

まとめ

最初分割法が複数あることに気付かずWA。
たとえばN=18の時、4+1+1=3+3かつ4*4+1*1+1*1=3*3+3*3=18だったりする。