diverta 2019 Programming Contest 2 C問題
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 - (残ったもう1つの数)とすればよい.つまり,
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) { // 負の数字を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;
}
この記事が気に入ったらサポートをしてみませんか?