いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

JAG夏合宿2011Day3F Beautiful Currency

問題

Beautiful Currency | Aizu Online Judge
数列が与えられる
数列の要素を変更してa_{i+1}%a_i==0になるようにしたい
仮にa_iからbに変えたいとき,変更コストを|a_i-b|/a_iとする
この変更コストの最大値の最小値を求める

考察

なんかDPっぽいんだけど制約が怪しくて間に合うかわからない
DPするならdp[i][j]を,数列のi番目の数をjにする時の最小コストとするとうまく行きそう
この時更新範囲はjの倍数の部分だけ行えばいいのでjを全探索すると
\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n-1}+\frac{n}{n}
になるのでO(NlogN)になる
これ知らんかった



ここで各aの変更する範囲が1e5ではダメでWAが出るんですけど,適当にどんなに大きくしても1e5*20でしょって思って出すとMLEする
答えは最大値の最小値なのでどんなに大きくても1以上にならないようにできるなぁと思うとa_n番目を頑張って変更する時が最大値になるのでa_n*2が最大とわかるので1e5*2まで変更すればいい

#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;
const int N_MAX=1e5*2+1;
 
signed main(){
  int n;
  cin>>n;
  vector<double> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  vector<vector<double> > dp(n+1,vector<double>(N_MAX,1e9));
 
  for(int i=1;i<N_MAX;i++){
    dp[0][i]=abs(a[0]-i)/a[0];
  }
 
  for(int i=1;i<n;i++){
    for(int j=1;j<N_MAX;j++){
      for(int k=j;k<N_MAX;k+=j){
        dp[i][k]=min(dp[i][k],max(dp[i-1][j],(abs(a[i]-k)/a[i])));
      }
    }
  }
 
  double ans=1e9;
  for(int i=1;i<N_MAX;i++){
    ans=min(ans,dp[n-1][i]);
  }
  cout<<fixed<<setprecision(20)<<ans<<endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3265223#1

まあ解説記事とか見つからなかったし知見も得たのでとりあえず記事にしたけど解説になってるかわからん許して