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

2014年06月25日20時40分18秒

Yandex.Algorithm 2014 Round 1 F問題 - Data Mining

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 1
問題文

問題概要

$N$ 個のサーバがあり，それぞれのサーバ $k$ のHDDには $A_i$ バイトのデータが入っている．
隣り合うサーバは繋がっていて，サーバ $i$ とサーバ $i+1$ は繋がっている．（サーバ $N$ とサーバ $1$ は繋がっていない）
$1$ 回の作業では，あるサーバ $x$ と，そのサーバに繋がっているサーバ $y$ を選び，サーバ $x$ のデータを全てサーバ $y$ にコピーする．
（サーバ $y$ のデータの容量が，サーバ $x$ のデータの容量だけ増える）
ちょうど $K$ 回だけ作業を行った後に，最もデータ容量の少ないサーバの容量を最大化したい．
その最大値を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

解法

$K < N$ の時は，$A_i$ のうち，小さい方から $K+1$ 番目の値が答え．
なぜなら，増やすことができるのは $K$ 回なので，小さい方から $k$ 要素をいくら増やしても，最小の要素として $K+1$ 番目に小さい $A_i$ は残るから．
逆に，小さい方から $K$ 個の要素はちゃんと小さい方から $K+1$ 番目の値を超えることができるかと言うとできる．
なぜなら，小さい方から $K$ 個の要素のうち，小さい方から $K$ 個の要素に含まれないものに接している部分からコピーしてくれば良い．
$K \geq N$ の時は，最初の $K-(N-1)$ 回はできるだけ大きい数を作って，残りの $N-1$ 回はその作った大きいデータを全体に順番にコピーしていく．
よって，$K-(N-1)$ 回で作れる最大の数が答えになる．
これは，隣り合うサーバで互いにコピーを繰り返せば良い．（途中で他のサーバのデータを使うなら，最初からそっちを使って互いにコピーしていったほうが良いことがわかる）
隣り合うサーバの最初のデータ容量を $x$ バイトと $y$ バイト（$x \geq y$）とすると，$m$ 回互いにコピーした後の大きい方のデータ容量は $x f_m + y f_{m-1}$ となる．
ここで，$f_k$ はフィボナッチ数．
よって，フィボナッチ数を最初に計算しておいて，全ての隣り合うサーバのペアに関して $K-(N-1)$ 回コピーを繰り返した後に最大のデータ容量と成るペアを探せば良い．
ただし，$K-(N-1)$ が大きい場合，$\verb|double|$ で計算してもオーバーフローしてしまうので，$K-(N-1)$ が大きい場合は大小比較する時のみ少し小さい値を用いるか，logと取って計算するなどする必要がある．
（$f_m/f_{m-1}$ の比率は収束していくので，$K-(N-1)$ がある程度大きければ，それ以上大きくなっても大小関係がひっくり返ることはなくなっていく，もしくはこの比率を用いて計算すれば良い）

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 MD 1000000007

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);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int K, N, A[20000];
ll f[2000000];
double ff[2000000];

int main(){
  int i, j, k;
  int fi, ffi;
  ll res;
  pair<int,int> mx, nw;
  double dmx, dtmp;

  reader(&K,&N);
  rep(i,N) reader(A+i);

  f[0] = 0;
  f[1] = 1;
  REP(i,2,2000000) f[i] = (f[i-1]+f[i-2]) % MD;

  ff[0] = 0;
  ff[1] = 1;
  REP(i,2,20000) ff[i] = ff[i-1]+ff[i-2];

  if(K >= N-1){
    fi = K - (N-1);
    ffi = min(200, fi);
    
    mx = make_pair(0,0);
    dmx = 0;
    REP(i,1,N){
      nw = make_pair(max(A[i-1],A[i]), min(A[i-1],A[i]));
      dtmp = nw.first * ff[ffi+1] + nw.second * ff[ffi];
      if(dmx < dtmp) dmx = dtmp, mx = nw;
    }

    res = mx.first * f[fi+1] + mx.second * f[fi];
    res %= MD;
  } else {
    sort(A, A+N);
    res = A[K];
  }

  writer(res, '\n');

  return 0;
}

Current time: 2024年04月25日03時07分36秒
Last modified: 2014年06月25日20時40分18秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round1
トップページに戻る

Logged in as: unknown user (not login)

ログイン：