100問マラソン 2問目 SRM 665 Div2 Hard: LuckySum

問題

LuckyNumberは全桁4,7で構成された数字のことを言う．LuckySumとはLuckyNumber2つの和である．
'?'または0-9で構成された文字列(note)が渡されるので，それに一致するような最小のLuckySumを求める．

制約

noteの文字数 <= 14

解法

下の桁から埋めるように全探索．写経．

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class LuckySum {

public:
	string note;
	long long INF;
	long long solve(int n,int up,bool secondEnd) {
		if(n == -1){
			if(up == 0)return 0;
			return INF;
		}

		long long ret = INF;
		vector<int> sum;
		if(secondEnd){sum.push_back(4);sum.push_back(7);}
		else{sum.push_back(11);sum.push_back(14);sum.push_back(8);}

		for(int i=0;i<sum.size();i++){
			sum[i] += up;
			if( note[n] == '?' || (sum[i]%10+'0') == note[n]){
				ret = min(ret, solve(n-1,sum[i]/10,secondEnd) * 10 + (sum[i]-up));
				if(!secondEnd)
					ret = min(ret, solve(n-1,sum[i]/10,true) * 10 + (sum[i]-up));
			}
		}
		if(n == 0 and up > 0 and (note[0] == '1' or note[0] == '?'))
						ret = min(ret,solve(n-1,0,secondEnd) * 10 );

		return ret;
	}

	long long construct(string note) {
		this->note = note;
		INF = 1e17;
		long long res = solve(note.size()-1, 0,false);
		if(res == INF)return -1;
		return res;
	}

};

本番中は分岐を全部書こうとして無限に時間を使っていた．こういう書き方できるようになりたい．
これで間に合うのか微妙な気がしたけど間に合うらしい．