[ARC130] C - Digit Sum Minimization
[Q] https://atcoder.jp/contests/arc130/tasks/arc130_c
かなり貪欲だけど1発で通る。ラッキーパンチあてたと思っている。
考察してみる。繰り上げ発生ごとに、桁の総和が9減少することに気づく。
Q. 入力例
A = 253
B = 266
・もし繰り上げがなければ
532
266
---
798 = 7+9+8 = 24
これは、全部の総和 2+5+3+2+6+6 = 24 と一致する。
・繰り上げが1回発生した場合は
532
662
----
1194 = 1+1+9+4 = 15
24-15 = 9
繰り上げが 1 回発生するごとに、桁の総和は、9 ずつ減少するのがわかる。 なので、繰り上げ回数を最大化すれば解答が得られると思う。
1. 桁が小さいほうをAにする。
2. とりあえず「10以上の組み合わせを1個見つける」を全探索する。
-3. 10以上の組み合わせが1個も作れない場合は終了。
-3. 作れた場合「9以上の組み合わせ数」が最も大きくなる[2.]を探す。
4. Aが全部繰り上がりになる場合、Bで残す9の数も繰り上げ数に含める。
5. [2.]の、最適な10以上の1つの組み合わせを決めたら、あとは9以上の組み合わせを機械的に採用する。
6. 残ったBを、大きい順に配置しておしまい。
Q. 入力例3
123
987987
1. A.size() < B.size() なので今回はABはそのまま。
2. 10以上の組み合わせを探して、見つかったら都度9以上の組み合わせ数を全探索していく。
・桁和10の場合
1) (A,B) = (1,9)がとれる。
1の位を固定する
A = XX1
B = XXXXX9
この状態から、9以上の組み合わせ数を探索する。
A = 321
B = 889779
がベスト。この繰り上がり数は、
A = 321
B = 889779
UUUU 4か所であがるので、4 繰り上がり。候補(1,9)をメモしておく
2) (A,B) = (2,8)がとれる。
1の位を固定する
A = XX2
B = XXXXX8
この状態から、9以上の組み合わせ数を探索する。
A = 312
B = 799788
がベスト。この繰り上がり数は、
A = 312
B = 799788
UUUUU 5か所であがるので、5 繰り上がり。候補(2,8)に更新する。
2) (A,B) = (3,7)がとれる。
1の位を固定する
A = XX3
B = XXXXX7
この状態から、9以上の組み合わせ数を探索する。
A = 213
B = 899787
がベスト。この繰り上がり数は、
A = 213
B = 899787
UUUUU 5か所であがるので、5 繰り上がり。更新しないのでスルー。
・桁和11の場合
(A,B) = {(2,9), (3,8)} の2通りも同様に探索するが、更新なし。
・桁和12の場合
(A,B) = {(3,9)} の1通りも同様に探索するが、更新なし。
5. 最適な1の位が(2,8) に定まる。
なので、あとは機械的に9以上の組み合わせを採用していく。
A = XX2
B = XXXXX8
A = 312
B = XXX788
6. B は 799 が残っている。大きい値から配置していく。
A = 312
B = 799788
これが解答。実装
string A, B;
ll asz, bsz;
ll numA[10]; // A="111" なら、numA[1]=3
ll numB[10];
bool sp = false; // Aの桁数が大きい場合ABをswap。その復元flag
// 桁和9以上の組み合わせが何通りできるか探索する
ll check2(ll defa, ll defb){// (defa,defb): 固定した1の位
ll testA[10];
ll testB[10];
rep(i, 10) testA[i] = numA[i];
rep(i, 10) testB[i] = numB[i];
--testA[defa];
--testB[defb];
ll ups = 0; // 桁和9以上の数
for(ll i=9; i<=18; ++i){ // 作りたい組み合わせの総和
for(ll a=i-9; a<=9; ++a){ // 8+9+8+7+6+...+1
if(a==0) continue;
ll b=i-a;
ll add = min(testA[a], testB[b]);
ups += add;
testA[a] -= add;
testB[b] -= add;
}
}
if (ups == asz-1){ // Aが全部繰り上げの場合、Bの"9"も繰り上げに含める
ups += testB[9];
}
return ups;
}
// 固定する1の位を探索
pll check(){
ll kumi=0;
pll ret = {0, 0}; // 固定する1の位の解答
for(ll i=10; i<=18; ++i){ // 作りたい組み合わせ 9+8+7+...+1
for(ll a=i-9; a<=9; ++a){
ll b=i-a;
ll add = min(numA[a], numB[b]);
if (add>0){ // もし桁和10以上の組み合わせが見つかったら
ll score = check2(a, b);
if (chmax(kumi, score)){
ret.first = a;
ret.second = b;
}
}
}
}
return ret;
}
int main(){
cincout();
cin >> A >> B;
stack<char> ansA; // 1の位から答えを入れていくのでstack
stack<char> ansB;
asz = A.size();
bsz = B.size();
if(asz>bsz){
swap(A, B);
asz = A.size();
bsz = B.size();
sp = true;
}
rep(i, asz) ++numA[A[i]-'0'];
rep(i, bsz) ++numB[B[i]-'0'];
// 固定する1の位を1つみつける。桁和10以上を1つだけ。
pll P = check(); // {a, b}
if (P.first==0){ // 繰り上げが1個もなければ終了
if(sp) swap(A, B); // わすれてた
cout << A << endl;
cout << B << endl;
return 0;
}
// 1の位を固定。
ansA.push(P.first+'0');
ansB.push(P.second+'0');
--numA[P.first];
--numB[P.second];
// 9以上の組み合わせを、桁和9から決定していく
for(ll i=9; i<=18; ++i){ // 作りたい組み合わせの桁和
for(ll a=i-9; a<=9; ++a){ // 8+9+8+7+...+1
if (a==0) continue;
ll b=i-a;
ll add = min(numA[a], numB[b]);
while(add>0){
ansA.push(a+'0');
ansB.push(b+'0');
--numA[a];
--numB[b];
--add;
}
}
}
// 9以上にできなかった桁和を、大きい値から入れていく。
for(ll i=9; i>=1; --i){
while (numA[i]>0){
ansA.push(i+'0');
--numA[i];
}
while (numB[i]>0){
ansB.push(i+'0');
--numB[i];
}
}
string AA, BB;
while (!ansA.empty()){
AA += ansA.top();
ansA.pop();
}
while (!ansB.empty()){
BB += ansB.top();
ansB.pop();
}
if (sp) swap(AA, BB); // もし入れ替えてたなら復元
cout << AA << endl;
cout << BB << endl;
}https://atcoder.jp/contests/arc130/submissions/27575870
Q.
1234
123
のとき？
A.
123
1234
になっちゃってた。繰り上がりがないときの復元swap忘れてた。救われた。