問題
http://community.topcoder.com/stat?c=problem_statement&pm=12045&rd=14738
ある数字が与えられる。
プレイヤーは好きな数字を２つもっており、それぞれ決められた個数だけ含んでいる数にしたい。
ある数字以上であり、かつ上記の条件を満たす最小の数字を求める。
解き方
全探索は１０＾１５のためできない。
まず必要な桁数は、もとの数字の桁数、もしくは好きな数字の数の合計、のいずれか大きい方になる。
次に例として、好きな数字が９が２つ、７が１つであるときを考える。
最初の数字を１２３４５６７８とすると、
４の桁の数字を一つ足すことで１２３５？？？？
？には好きな数字を入れることができるので、最適な数字を入れることで探索範囲を狭めることができる。
ここでいう最適な数字とは、以下になることがわかる。
（０＊？の残りの桁）＋（小さい数字＊必要数）＋（大きい数字＊必要数）
上記の例では「１２３５０７９９」となる。
つまり、少ない数字から足していく方法が最初に思い浮かぶが、
大きい数字から考えるとシンプルに実装することができる。
あとは元の数字から１を引き、それより大きい数字を左から全て探索する。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FavouriteDigits {
public:
string tostring(long long x){
string str;
stringstream out;
out<<x;
out>>str;
return str;
}
long long findNext(long long llN, int digit1, int count1, int digit2, int count2) {
if(digit1>digit2){
swap(digit1,digit2);
swap(count1,count2);
}
char d1=digit1+'0';
char d2=digit2+'0';
string N=tostring(llN-1);
int L=max((int)N.size(),count1+count2);
N=string(L-N.size(),'0')+N;
int cc1=max(0,count1-(d1=='1'));
int cc2=max(0,count2-(d2=='1'));
string ret='1'+string(L-cc1-cc2,'0')+string(cc1,d1)+string(cc2,d2);
FORE(i,0,L){
for(char ch='9';ch>N[i];ch--){
int c1=max(0,count1-(d1==ch));
int c2=max(0,count2-(d2==ch));
if(L-i-1>=c1+c2){
string tmp=N.substr(0,i)+ch+string(max(0,L-i-1-c1-c2),'0')+string(c1,d1)+string(c2,d2);
if(tmp[0]!='0')ret=tmp;
}
}
count1-=(d1==N[i]);
count2-=(d2==N[i]);
}
long long num=0;
stringstream out(ret);
out>>num;
return num;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FavouriteDigits {
public:
string tostring(long long x){
string str;
stringstream out;
out<<x;
out>>str;
return str;
}
long long findNext(long long llN, int digit1, int count1, int digit2, int count2) {
if(digit1>digit2){
swap(digit1,digit2);
swap(count1,count2);
}
char d1=digit1+'0';
char d2=digit2+'0';
string N=tostring(llN-1);
int L=max((int)N.size(),count1+count2);
N=string(L-N.size(),'0')+N;
int cc1=max(0,count1-(d1=='1'));
int cc2=max(0,count2-(d2=='1'));
string ret='1'+string(L-cc1-cc2,'0')+string(cc1,d1)+string(cc2,d2);
FORE(i,0,L){
for(char ch='9';ch>N[i];ch--){
int c1=max(0,count1-(d1==ch));
int c2=max(0,count2-(d2==ch));
if(L-i-1>=c1+c2){
string tmp=N.substr(0,i)+ch+string(max(0,L-i-1-c1-c2),'0')+string(c1,d1)+string(c2,d2);
if(tmp[0]!='0')ret=tmp;
}
}
count1-=(d1==N[i]);
count2-=(d2==N[i]);
}
long long num=0;
stringstream out(ret);
out>>num;
return num;
}
};