Codeforces Round #350 (Div. 2) F. Restore a Number
問題
Problem - F - Codeforces
AさんはBさんにある数字にその数字の長さを右に付け足して送った.しかし,送られる途中で文字の順番がバラバラになってしまった.Aさんはその数字の部分列を覚えている.送った可能性のある数字の内,その部分列を含むような最小の数字はいくつか.
解法
まず,送った数字の長さは一意に決めることができる.条件を満たすような数字の長さが1つ見つかったとする.この長さに1足したものでも条件を満たすと仮定すると元の数字の長さが1つ増えるのでそれに付け足す数字の長さの部分は1減らなければいけない.しかし,1足しているのでそのようなことは起こりえない.逆も同様である.
長さがわかったので使う文字をカウントし,Aさんが覚えている部分列を含むように最小の数字を探せば良い.
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP(i,(int)(n)-1,0) #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP(i,0,(int)(n)-1) #define INF 100000000 typedef long long ll; int main() { int i, j; int num[10] {}; bool small, large; string d, sub; cin >> d >> sub; int sz = d.size(); for (auto c : d) num[c-'0']++; if (sz >= 100006) sz -= 6; else if (sz >= 10005) sz -= 5; else if (sz >= 1004) sz -= 4; else if (sz >= 103) sz -= 3; else if (sz >= 12) sz -= 2; else sz -= 1; while (sz > 0) { num[sz%10]--; sz /= 10; } small = large = false; i = sub[0] - '0'; for (auto c : sub) { if (!small && !large) { if (i > c - '0') small = true; else if (i < c - '0') large = true; } num[c-'0']--; } i = 1; while (i < 10 && !num[i]) i++; if (sub[0] == '0' || num[0] > 0) { if (i == sub[0] - '0') { REP (j,1,sub.size()-1) if (sub[j] != '0') break; j--; if (num[0] < j) { cout << sub; sub[0] = 0; } else { cout << i; num[i]--; } } else if (i > sub[0] - '0' && sub[0] > '0') { cout << sub; sub[0] = 0; } else if (i < 10) { cout << i; num[i]--; } } rep (i,10) { if (sub[0] == i + '0' && !small && !large) cout << sub; if (sub[0] == i + '0' && small) cout << sub; rep (j,num[i]) cout << i; if (sub[0] == i + '0' && large) cout << sub; } cout << endl; return 0; }
場合分けが大変だったがいつものCodeforcesならCとかで出てきそうな問題だった.