ARC092 E : Both Sides Merger(700)
作成日：2018.08.15
最終更新日：2018.08.15
問題概要
長さ$N$の数列$\{a_i\}$が長さ$1$になるまで、操作「数列の要素を1つ選び、それが端だったら削除する。そうでない時、その要素を両隣の要素の和に書き換え、両隣の要素を削除する。」を繰り返す。
残った数列の要素の値の最大値と、それを達成する操作の手順を求めよ。
制約
$2 \leq N \leq 1000$
$|a_i| \leq 10^9$
考え方
答えは数列の要素の1つ以上の和であるから、どの要素を同時に和に組み込めるかを考える。
操作では1つ飛んだ位置にある要素を組み込むことができる。
この操作を行ってもまとめる前の要素から1つ飛んだ位置にある要素は変わらないことから、同時に和に組み込めるのは初めの数列での添え字の偶奇が同じ要素だけであることが分かる。
次に偶数(奇数)番目の要素それぞれにおいて和に組み込むか否かを選択できるかを考える。
ある要素を組み込まないと決めたとすると、操作でその要素を選べば削除されるのでこれは達成できる。
またこの時他の偶数(奇数)番目の要素には影響しないので、組み込まない要素をすべて削除した後に奇数(偶数)番目の要素それぞれに操作を行えば選んだものすべてを和に組み込める。
以上より、要素を偶数番目と奇数番目に分け、正である要素の和が大きい方の正である要素をすべて選択すれば良いことが分かる。
但し数列の要素がいずれも$0$以下である場合は、最大の要素だけを選ばなければならないことに注意する。
また、操作の手順は先に述べた通りにすれば良い。
ソースコード
マクロ等はこちら
const int MC = 1024;
int N;
LL a[MC];
bool b[MC]; //和に組み込むならtrue
int main(){
cin >> N;
repp(i,0,N) cin >> a[i];
LL ans0 = 0 , ans1 = 0;
bool c = 0; //正整数が存在するかのフラグ
for(int i = 0 ; i < N ; i += 2){
if(a[i] > 0){
ans0 += a[i];
b[i] = 1;
c = 1;
}
}
for(int i = 1 ; i < N ; i += 2){
if(a[i] > 0){
ans1 += a[i];
b[i] = 1;
c = 1;
}
}
if(c){
if(ans0 > ans1){
for(int i = 1 ; i < N ; i += 2) b[i] = 0;
} else {
for(int i = 0 ; i < N ; i += 2) b[i] = 0;
}
cout << max(ans0,ans1) << endl;
} else {
int d = 0;
repp(i,1,N){
if(a[d] < a[i]) d = i;
}
cout << a[d] << endl;
b[d] = 1;
}
vector<int> V;
int p = 0 , r = 0;
while(!b[p]){
V.PB(1);
++p;
++r;
}
while(p < N){
int q = p+1;
while(!b[q] && q < N) ++q;
if(q == N) break;
repm(i,(q-p)/2,0){
V.PB(p+1-r+i);
}
r += q-p;
p = q;
}
repm(i,N-r,1) V.PB(i);
cout << V.size() << endl;
for(auto u : V) cout << u << endl;
return 0;
}解法まとめ
正の要素が存在しなければ、答えは$max(a_i)$である。(33-38行)
正の要素が存在する場合は、偶数番目の要素で正のものの和と奇数番目の要素で正のものの和のうち大きい方が答えである。(9-24,26-31行)
操作の手順は、和に組み込む要素と位置の偶奇が等しい要素で和に組み込まないものをすべて選んだ後、和に組み込む要素と位置の偶奇が異なる要素をすべて選べば良い。
但し上のソースコードでは、和に組み込む要素が先頭になるまで先頭から組み込まない要素を選んでいき、組み込む要素同士のちょうど中間にあるものを先頭に近いものから選んだ後、末尾から組み込まない要素すべてを選んでいる。(40-59行)