[ARC130] C - Digit Sum Minimization
見出し画像

[ARC130] C - Digit Sum Minimization

syamashi

[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忘れてた。救われた。

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
তরকারীও রয়েছে
syamashi
非エンジニア。atcoder(highest:1844)/42Tokyo2月1期(pass)/セミリタイア(20190702最終出社)