https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_c

2019年6月15日開催のdiverta 2019 Programming Contest 2 に参加した．B問題の私の理解と解説．

C - Successive Subtraction

問題文はこちら．

今，与えられた数列A_1, A_2 ... がa, b, c, d, eのとき，最後に残る数字は，たとえば

a, b, c, d, e
→ (b-a), c, d, e
→ (b-a), (d-c), e
→ (d-c)-(b-a), e 
→ e - ((d-c)-(b-a))= - a + b + c - d + e

のようになる．いくつか操作の順番を試してみれば，ただ 1つ残る整数は 

±a ±b ±c ±d ±e (複号は全て同じである場合を除いて任意)

とできるとわかる．ただし，全てマイナス，もしくは全てプラスにすることだけはできない．これが最大になる時を考える．

残る数字が最大になるのは，次の3つの場合に分けられる．

1. 与えられた数列がすべて負の時

最大になるのは，数列のうち最大の数がの複号をマイナス，それ以外をプラスにしたとき．例えば，a <= b <= c <= d <= e <0 のとき残る数字が最大になるのは

M = - a - b - c - d + e 

のときで，これを作るには，eを最初のxにし，a~dを大きい方から順次引いていけばよい．つまり

a, b, c, d, e
→ e-d, a, b, c,
→ e-d - c , a, b
→ e-d-c - b, a
→ e-d-c-b - a = M

2. 与えられた数列のうち0以上が1個以上あり，負が2個以上あるとき

負の数の複号をマイナス，それ以外をプラスにすれば，残る数字は最大になる．例えば，a <= b <= c < 0 <= d < e のとき

M = - a - b - c + d + e

となる．これの作り方は，まず，負の数が残り1つになるまで e - (負の数)を行う．そのあとは 「3. 与えられた数列のうち0以上が1個以上あり，負が1個以下の とき」に帰着する．

a, b, c, d, e
→ e-a, b, c, d
→ (e-a-b), c, d ... (c < 0 <= d < (e-a-b) ... 0以上が1個以上あり負が1個以下)

3. 与えられた数列のうち0以上が1個以上あり，負が1個以下のとき

最小の数字の複号をマイナス，それ以外をプラスにすれば，残る数字は最大になる．例えば a <= b <= c <= d < e (b>=0) のとき，

M = -a + b + c + d +e 

となる．これの作り方は，最初のxにaを選び，b~dを小さい方から順次引いていき，最後にe - (残ったもう１つの数)とすればよい．つまり，

a, b, c, d, e
→ a - b, c, d, e
→ a-b - c, d, e
→ a-b-c - d, e
→ e-(a-b-c-d)= -a + b + c + d +e = M

 C++ の実装例は以下(#include は省略)

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
 int N, neg=0;// neg; 負のAiの個数
 cin >> N;
 vector<int> A(N);
 rep(i, N) {
     cin >> A[i];
     if(A[i]<0) neg++;
 }
 sort(A.begin(), A.end());

 vector<int> x(N-1), y(N-1);
 int start = 0;
 int tmp = 0;
 
 if(neg==N) { // 1. 与えられた数列がすべて負の時
   x[0] = A[N-1]; 
   y[0] = A[N-2];
   tmp = x[0] - y[0];
   for(int i=1; i<N-1; i++) { // 大きい方から順番に引き算
       x[i] = tmp;
       y[i] = A[N-i-2];
       tmp = x[i] - y[i];
   }
 }
 else if(neg>1) { // 2. 与えられた数列のうち0以上が1個以上あり，負が1個以下のとき
   rep(i, neg-1) {   // 負の数字を１つ残してA[N-1]にねじ込む
       x[i] = A[N-1]; // max
       y[i] = A[i]; // 負
       A[N-1] = A[N-1] - A[i];
   }
   start = neg-1; //最大N-2

   if(start<N-2) {
       x[start] = A[start];
       y[start] = A[start+1];
       tmp = x[start] - y[start];
       for(int i=start+1; i<N-2; i++){ // small - big
           x[i] = tmp;
           y[i] = A[i+1];
           tmp = x[i] - y[i];
       }
       // 最後の一回は A[N-1] - tmp
       x[N-2] = A[N-1];
       y[N-2] = tmp;
       tmp = x[N-2] - y[N-2];
   } else { // start == N-2
       // 最後の一回は A[N-1] - tmp
       x[N-2] = A[N-1];
       y[N-2] = A[N-2];
       tmp = x[N-2] - y[N-2];
   }

 }
 else { // 3. 与えられた数列のうち0以上が1個以上あり，負が1個以下のとき
   x[0] = A[0];
   y[0] = A[1];
   tmp = x[0] - y[0];
 
   for(int i=1; i<N-2; i++){ // 小さい方から順番に引き算
     x[i] = tmp;
     y[i] = A[i+1];
     tmp = x[i] - y[i];
   }
   // 最後の一回は A[N-1] - tmp
   x[N-2] = A[N-1];
   y[N-2] = tmp;
   tmp = x[N-2] - y[N-2];
 }

 cout << tmp << endl; // tmp = M 
 rep(i, N-1) {
     cout << x[i] << ' ' << y[i] << endl;
 }

 return 0;
}

別解

場合分けを全て正，全て負，その他，にしてみた．あまりコードは綺麗になっていない．

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
 int N, neg=0, pos=0;// neg; 負のAiの個数 ,pos 正の．
 cin >> N;
 vector<int> A(N);
 rep(i, N) {
     cin >> A[i];
     if(A[i]<0) neg++;
     else if(A[i]>0) pos++;
 }
 sort(A.begin(), A.end());

 vector<int> x(N-1), y(N-1);
 int start = 0;
 int tmp = 0;

 if(neg==N) { // 全て負の時
   x[0] = A[N-1]; 
   y[0] = A[N-2];
   tmp = x[0] - y[0];
   for(int i=1; i<N-1; i++) {
       x[i] = tmp;
       y[i] = A[N-i-2];
       tmp = x[i] - y[i];
   }
 } else if(pos==N) { // 全て正の時
   x[0] = A[0];
   y[0] = A[1];
   tmp = x[0] - y[0];
 
   for(int i=1; i<N-2; i++){ // small - big
     x[i] = tmp;
     y[i] = A[i+1];
     tmp = x[i] - y[i];
   }
   // 最後の一回は A[N-1] - tmp
   x[N-2] = A[N-1];
   y[N-2] = tmp;
   tmp = x[N-2] - y[N-2];
 }
 else { // 正，負がともにN個未満
   // 負の数字が1個になるまでA[N-1]から 0以下の数字を引く
   // 負の数字が0個のとき，正の数字がN個未満なので，0が1個以上のこる．
   int i = 0;
   for(; i<neg-1; i++) {
     x[i] = A[N-1];
     y[i] = A[i];
     A[N-1] = x[i] - y[i];
   } 
   if(i<N-2) {
     x[i] = A[i];
     y[i] = A[i+1];
     tmp = x[i] - y[i];
     i++;
     for(; i<N-2; i++) {
       x[i] = tmp;
       y[i] = A[i+1];
       tmp = x[i] - y[i];
     }
     // 最後の1回は  A[N-1] - tmp
     x[N-2] = A[N-1];
     y[N-2] = tmp;
     tmp = x[N-2] - y[N-2];
   }
   else { // i == N-2, 最後の1回
     x[N-2] = A[N-1];
     y[N-2] = A[N-2];
     tmp = x[N-2] - y[N-2];
   }
 }
 
 cout << tmp << endl; // tmp = M 
 rep(i, N-1) {
     cout << x[i] << ' ' << y[i] << endl;
 }

 return 0;
}

追記: シンプルな実装

わかりやすい実装の提出を見つけたのでリンクを貼っておく．

この実装では，与えられた数列を
a, b, c, d, e (a<=b<=c<=d<=e)
とした時，最後に残る整数
±a ±b ±c ±d ±e
が最大になるのは，a(最小)の前の複号が - , e(最大) の複号が + の時に限ることに着目している．このnoteの上の例も全てそうなっている．

Mの作り方は，a, e (最小と最大)以外のb, c, d のうち0未満のものをeから引き，0以上のものをa から引く．最後に残った2数で引き算をする．

a, b, c, d, e (a<=b<0<=c<=d<=e とする)
→ a, c, d, e - b
→ a - c, d, e-b
→ a-c - d, e-b
→ (e-b)-(a-c-d)= -a - b + c + d + e = M

自分で再実装してみた例:

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
 int N;
 cin >> N;
 vector<int> A(N);
 rep(i, N) {
     cin >> A[i];
 }
 sort(A.begin(), A.end());

 vector<int> x(N-1), y(N-1);
 int tmp_large = A[N-1];
 int tmp_small = A[0];
 for(int i=0; i<N-2; i++) {
   if(A[i+1]<0) {
     x[i] = tmp_large;
     y[i] = A[i+1];
     tmp_large = x[i] - y[i];
   } else  {
     x[i] = tmp_small;
     y[i] = A[i+1];
     tmp_small = x[i] - y[i];
   }
 }
 // 最後の一回 
 x[N-2] = tmp_large;
 y[N-2] = tmp_small;
 int M = x[N-2] - y[N-2];
 
 cout << M << endl; // tmp = M 
 rep(i, N-1) {
   cout << x[i] << ' ' << y[i] << endl;
 }

 return 0;
}