kurarrr's memooo

主に競プロ備忘録

ARC 086 D - Non-decreasing (600)

問題概要

N個の整数からなる数列が与えられる.
x,yについて,a[y]にa[x]を足す,という操作を繰り返して,
a[0] <= a[1] <= ... <= a[N] を満たすようにしたい.
条件を満たす2N回以内の操作を出力せよ.
そのような操作が存在することは保証されている.
2 <= N <=50 , abs(a[N]) <= 106

解法

a[i]が全て正の時, a[1] += a[0], a[2] += a[1],..., a[N-1] += a[N-2]
とすれば, 新しいa'[i]はa[i]の累積和となり条件を満たす.
全て負の時は a[N-2] += a[N-1], ... a[0] += a[1]とすれば良い.

正負が混じっている時,min(a[i]) < 0 , max(a[i]) >= 0 であり,
abs(min(a[i])) > abs(max(a[i])) の時は全てのa[i]にminを,
そうでない時は全てのa[i]にmaxを足せば上に帰着できる.

メモ

最小手数のものを求めよかと思っていた.日本語力.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 51;
int a[MAX_N];

vector<P> ans;

int main(){
  int N; cin >> N ;
  int _min = INF, _max = -INF;
  int argmin,argmax;
  rep(i,N){
    scanf("%d",a+i);
    if(a[i]<_min){
      _min = a[i];
      argmin = i;
    }
    if(a[i]>_max){
      _max = a[i];
      argmax = i;
    }
  }
  if(_min<0 && _max>0){
    if(abs(_min)>abs(_max)){
      // 全部負にする
      rep(i,N){
        if(a[i]<0) continue;
        ans.pb(P(argmin+1,i+1));
      }
    }else{
      // 全部正にする
      _min = 1;
      rep(i,N){
        if(a[i]>0) continue;
        ans.pb(P(argmax+1,i+1));
      }
    }
  }
  if(_min>=0){
    rep(i,N-1) ans.pb(P(i+1,i+2));
  }else{
    for(int i=N;i>1;i--) ans.pb(P(i,i-1));
  }
  cout << ans.size() << endl;
  rep(i,ans.size()) cout << ans[i].first << " " << ans[i].second << endl;
  return 0;
}