保存されている過去のバージョンの一覧

2015年08月16日04時38分14秒

AtCoder Regular Contest #043 D問題 - 引っ越し

Source

AtCoder Regular Contest #043
問題文

問題概要

$N$ 個の家が一直線上に等間隔に並んでいて，隣り合う家の距離は $1$ である．
$M$ 個の家族がいて，$i$ 番目の家族は $P_i$ 人家族である．
$M$ 個の家族がそれぞれ相異なる $1$ つの家に住む．
その際，相異なる全ての人のペアに対して住んでいる家の距離の和を考え，その値を最大化したい．
最大値を求める問題．

解法

相異なる全ての人のペアに対して住んでいる家の距離の和，というのは，見方を変えると，
各家と家の間に関して，それより左に住んでいる人の人数とそれより右に住んでいる人の人数の積，の和を取れば良い．
また，できるだけ人数の多い家族を端に配置した方が良いので，人数の多い方から開いている家のうち左右どちらの端に割り振るかを試していけば良い．
よって，家族は人数の多い順にソートしておき，（今何番目家族まで配置したか，左端に配置した人の人数の和）を状態に取り，既に左右どちらかが埋まっている家と家の間に対して，それより左に住んでいる人の人数とそれより右に住んでいる人の人数の積の和の最大値を計算する．
最後に，余っている家と家の間 $N-M+1$ 個分について，左に配置した人数から，それより左に住んでいる人の人数とそれより右に住んでいる人の人数の積を計算し足して，最大となるものを調べれば良い．
人数の最大値は $M \max(P_i)$ なので，状態数は $O(M^2 \max(P_i))$ となるが，今なん番目の家族まで配置したかは直近のものだけ覚えておけば良いので，
時間計算量は $O(M^2 \max(P_i))$，空間計算量は $O(M \max(P_i))$ となる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

char memarr[17000000]; void *mem = memarr;

template<class S, class T> inline void chmax(S &a, T b){if(a<b)a=b;}
template<class T> void *malloc1d(T **arr, int x, void *mem){(*arr)=(T*)mem;return((*arr)+x);}

int N, M, P[1000];
ll *dp, *nx;
ll pre[111111];

int main(){
  int i, j, k;
  int sum, mm, ed, now;
  ll res, tmp;

  reader(&N,&M);
  rep(i,M) reader(P+i);
  sort(P, P+M);
  reverse(P, P+M);

  sum = 0;
  rep(i,M) sum += P[i];

  mem = malloc1d(&dp, sum+111, mem);
  mem = malloc1d(&nx, sum+111, mem);

  mm = sum/2 + 3;

  rep(i,sum+1) pre[i] = (ll)(sum-i)*i;

  dp[0] = 0;
  ed = 1;
  now = 0;
  rep(i,M){
    rep(j,ed+P[i]) nx[j] = -1;
    rep(j,ed) if(dp[j]>=0){
      chmax(nx[j], dp[j]+pre[now-j]);
      chmax(nx[j+P[i]], dp[j]+pre[j]);
    }
    swap(dp,nx);
    now += P[i];
    ed = min(ed+P[i], mm);
  }

  res = 0;
  rep(i,mm) if(dp[i]>=0){
    chmax(res, dp[i]+(ll)(N-M+1)*i*(sum-i));
  }

  writerLn(res);

  return 0;
}

Current time: 2024年04月19日16時32分32秒
Last modified: 2015年08月16日04時38分14秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC043 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：