yukicoder : No.1953 ８

割と素直な問題。
https://yukicoder.me/problems/no/1953

問題

1～Nの整数をすべて書きだしたとき、閉曲線が計K個あった。
Kが与えられたとき、条件を満たすNが存在すれば1つ答えよ。

解法

f(N) := N以下の正整数をすべて書きだしたときの閉曲線の個数
とすると、fは単調増加なのでNを二分探索すればよい。
Nが求まれば、あとは桁DPの要領で上の桁から0～9を順次埋めて行くケースをメモ化再帰で求めて行くだけ。

ll K;

int C[10]={1,0,0,0,1,0,1,0,2,1};
pair<ll,ll> dp[20][2][2];
string S;

pair<ll,ll> hoge(int d,int le,int lz) {
	if(d<0) return {lz,0};
	if(dp[d][le][lz].first>=0) return dp[d][le][lz];
	ll sum=0;
	ll num=0;
	
	int c;
	FOR(c,10) {
		if(le==0&&c>S[d]) break;
		pair<ll,ll> r=hoge(d-1,le|(c<S[d]),lz|(c>0));
		num+=r.first;
		sum+=r.second;
		if(c>0||lz) sum+=r.first*C[c];
	}
	
	
	return dp[d][le][lz]={num,sum};
	
}

ll num(ll v) {
	S=to_string(v);
	reverse(ALL(S));
	S+="000000000000000000";
	FORR(c,S) c-='0';
	MINUS(dp);
	
	return hoge(19,0,0).second;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>K;
	ll ret=1LL<<60;
	for(i=59;i>=1;i--) if(num(ret-(1LL<<i))>=K) ret-=1LL<<i;
	
	if(num(ret)==K) {
		cout<<ret<<endl;
	}
	else {
		cout<<-1<<endl;
	}
	
}

まとめ

なんで問題名が8なんだろうな。閉曲線がこれだけ2個あるから？