CSAcademy Round #39 : D. Seven-segment Display

C,DでグダったけどEが解けたので助かった。
https://csacademy.com/contest/round-39/task/seven-segment-display/

問題

電卓などで使われるSeven Segment Displayを考える。
点灯する棒の数がKとなる整数のうち最小のものを答えよ。

解法

桁数は少なければ少ないほどいいので、基本的に棒が最多7本である8を埋めていく。
Kが8の倍数でない場合余るのでちょっと工夫が必要になる。
自分は上位7桁位は総当たりし、残りは8で埋めるという方針を取った。

Leading Zeroが認められないため、K=18の時など600が最適解となる点に注意。

ll K;
int S[10]={6,2,5,5,4,5,6,3,7,6};
string C;

string cand[70];

void dfs(string s,int left,int hoge) {
	sort(ALL(s));
	if(s.size()>1 && s[0]=='0') {
		int i;
		FOR(i,s.size()) if(s[i]!='0') {
			swap(s[i],s[0]);
			break;
		}
	}
	if(count(ALL(s),'0')!=s.size()) {
		if(cand[hoge]=="*" || s.size()<cand[hoge].size() || (s.size()==cand[hoge].size() && s<cand[hoge])) cand[hoge]=s;
	}
	
	if(left==0) return;
	for(int i=2;i<=7;i++) {
		dfs(s+C[i],left-1,hoge+i);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	C.resize(10);
	for(i=9;i>=0;i--) C[S[i]]='0'+i;
	
	FOR(i,70) cand[i]="*";
	dfs("",7,0);
	
	cin>>K;
	if(K==6) {
		cout<<0<<endl;
		return;
	}
	string R;
	for(i=2;i<70;i++) {
		if(cand[i]!="*" && K>=i && (K-i)%7==0) {
			string T=cand[i]+string((K-i)/7,'8');
			if(R.empty() || T.size()<R.size() || (T.size()==R.size() && T<R)) R=T;
		}
		
		if(i%6==0 && K>=i && (K-i)%7==0) {
			string T="6"+string(i/6-1,'0') + string((K-i)/7,'8');
			if(R.empty() || T.size()<R.size() || (T.size()==R.size() && T<R)) R=T;
		}
	}
	
	if(R.empty()) R="-1";
	cout<<R<<endl;
}

まとめ

CもDもコーナーケースが多くて手間取った。