読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Codeforces Round #350 (Div. 2) F. Restore a Number

codeforces

問題
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とかで出てきそうな問題だった.