ARC086 D : Non-decreasing(600)
作成日：2017.12.12
最終更新日：2017.12.12
問題概要
長さ$N$の数列$\{a\}$がある。
操作「$1$以上$N$以下の整数$x,y$を選び、$a_y$に$a_x$を加算する」を$2N$回以下行うことで数列$\{a\}$が広義単調増加するようにしたい。
そのような操作手順を1つ求めよ。
制約
$2 \leq N \leq 50$
$-10^6 \leq a_i \leq 10^6$
考え方
$a_i$は負にもなり得るが、まずはすべて負でないとして考える。
2つの非負整数$s,t$において必ず$s < s+t$が成り立つから、$i$が小さいものから$a_{i+1}$に$a_i$を加算していけば条件を満たす。
逆を考えれば$a_i$がすべて正でない時にも条件を満たす数列を構成できることが分かる。
以上より、$a_i$をすべて非負または非正にできれば良いことが分かる。
そのためには絶対値が最大のものを取ってきてすべての要素に足せばよい。
この$a_i$の正負を揃えるために$N$回、その後に数列を広義単調増加にするために$(N-1)$回の操作が必要だが、これは問題の条件に反しない。
ソースコード
マクロ等はこちら
int N;
int a[55];
vector<P2> ans;
int main(){
cin >> N;
int mx = -12345678 , mn = 12345678;
int s = -1 , t = -1;
repp(i,0,N){
cin >> a[i];
if(a[i]>mx){
mx = a[i];
s = i;
}
if(a[i]<mn){
mn = a[i];
t = i;
}
}
if(mx > -mn){
repp(i,0,N) if(a[i] <= 0){
ans.PB(MP(s,i));
a[i] += a[s];
}
repp(i,1,N){
if(a[i-1] > a[i]){
ans.PB(MP(i-1,i));
a[i] += a[i-1];
}
}
} else {
repp(i,0,N) if(a[i] >= 0){
ans.PB(MP(t,i));
a[i] += a[t];
}
repm(i,N-1,0){
if(a[i-1] > a[i]){
ans.PB(MP(i,i-1));
a[i-1] += a[i];
}
}
}
cout << ans.size() << endl;
for(auto z : ans) cout << z.first+1 << ' ' << z.second+1 << endl;
return 0;
}解法まとめ
絶対値が大きいものが正であったら、すべての要素にそれを加えて非負にした後、数列の先頭から$a_i$に$a_{i-1}$を加えて広義単調増加数列にする。(21-30行)
そうでない時、絶対値が最大のものをすべての要素に加えて非正にした後、数列の後ろから$a_{i-1}$に$a_i$を加えて広義単調増加数列にする。(32-41行)