CF 670 F - Restore a Number
問題
問題概要
ある数字があり,それにの桁数を合わせて書いておいた紙があったが,桁の順番がめちゃくちゃになってしまった.(例:として3342が与えられる時,その桁数は4なので紙には33424と書かれるがその順番が入れ替わって34342のような文字列が得られる.)
今,として書いたものが何であったか,の部分列(この問題において,のある連続している部分のことを指す)しか思い出すことが出来ない.
紙に書かれた文字列との部分列であるが与えられる時,の値としてあり得る最小の値を求めよ.
- が空文字列であることはない
- の先頭に0がくるのはが0であるときしかありえなく,leading zeroは無い.
- 入力は正当なものであり,として取ることの出来る値が無いことはありえない.
アイデア
まずは,与えられた文字列に関して,桁数を表すとしての数字なのか,の桁の1つとしてその数字が入っているのかを判別したい.
条件から,桁数は必ず999999以下になるはずであるから,の桁数に関して,ということになる.そして,桁数として使用されない文字は全てとして使われているはずなのでを満たすときに,以下のことをためして最小値を更新していけば良い.
まず,である.この数字をから取り出すことが出来るか調べる.取り出すことが可能(そもそもその数字があるか・取り除いた後の数だけで部分列を構成することは可能か)ならその数字を取り除いて2.へ進む.
このステップにたどり着く時はとして値を構成することが出来ることが保証されている.残っている数で,部分列を含むようにできるだけ小さい値を作りたい.それは次の3つのうちどれかになる(様々な条件を考えることで試す前に1つに絞り込むことも可能だとは思うが,それよりは試してしまう方が計算時間もそんなに掛かるものではないし,手っ取り早い):
(1) が先頭に来て,その後ろに小さい順に残った数
(2) が先頭に来て,その後ろに以下の数が小さい順に並び,が入って,その後ろにより大きい数が小さい順に並ぶ
(3) が先頭に来て,その後ろに未満の数が小さい順に並び,が入って,その後ろに以上の数が小さい順に並ぶ
これらの中で作成可能なものから最小を選び,最小値を更新していけば良い.
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second int main() { string s,t; cin >>s >>t; //答えが0になる場合のみ排除 if(s=="01" || s=="10") { printf("0\n"); return 0; } int S=s.size(); //各数字が何個あるかカウント vector<int> ct(10,0); rep(i,S) ++ct[s[i]-'0']; //10のi乗 int p10[7]; p10[0]=1; for(int i=1; i<=6; ++i) p10[i]=10*p10[i-1]; //tに含まれる文字を予め除いておく rep(i,t.size()) --ct[t[i]-'0']; string ans="#"; for(int x=1; x<=6; ++x) { int d=S-x; if(p10[x-1]<=d && d<=p10[x]-1) { vector<int> tct(ct); //桁数として使われる数を除く int td=d; while(td>0) { --tct[td%10]; td/=10; } //このような構成は不可能 rep(i,10) { if(tct[i]<0) continue; } string tmp=""; //残った0以外の数の中で最小のもの int h1=1; while(h1<10 && tct[h1]==0) ++h1; //tの先頭 int h2=t[0]-'0'; //tが絶対先頭に来る場合 if(h2!=0 && h2<h1) { tmp+=t; rep(i,10)rep(j,tct[i]) tmp+=i+'0'; } else { string t1="", t2="", t3=""; //t1の構成 if(t[0]!='0') { t1+=t; rep(i,10)rep(j,tct[i]) t1+=i+'0'; } //t2とt3の構成 if(h1<10) { t2+=h1+'0'; t3+=h1+'0'; --tct[h1]; for(int i=0; i<h2; ++i)rep(j,tct[i]) { t2+=i+'0'; t3+=i+'0'; } t2+=t; rep(i,tct[h2]) t2+=h2+'0'; rep(i,tct[h2]) t3+=h2+'0'; t3+=t; for(int i=h2+1; i<10; ++i)rep(j,tct[i]) { t2+=i+'0'; t3+=i+'0'; } } //3つの中で最小値を選ぶ if(t1!="") tmp=t1; if(t2!="") { if(tmp=="") tmp=t2; else tmp=min(tmp,t2); } if(t3!="") { if(tmp=="") tmp=t3; else tmp=min(tmp,t3); } } //最小値を更新 if(ans=="#") ans=tmp; else { if(ans.size()>tmp.size()) ans=tmp; else if(ans.size()==tmp.size()) ans=min(ans,tmp); } } } cout << ans << endl; return 0; }