Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2327-93f8c2eb
この記事にトラックバックする(FC2ブログユーザー)

ARC 008 D - タコヤキオイシクナール (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N個の箱がある.
各箱iにはパラメータa[i], b[i]が設定されている.(a[i], b[i]の絶対値は1以下)
箱iに数xを入れると,f_i(x) = a[i] * x + b[i]となって出てくる.
最初はa=1, b=0に設定されている.
M回だけ,ある1個の箱を指定して,パラメータを変える操作を行った履歴が与えられる.
また,パラメータを変更する前,各変更の後,合計M+1回だけ,
 箱1に1を入れて,出てきた数字を箱2に入れて,…,出てきた数字を箱Nに入れて出てきた数字を調べる
ということを行った.
つまり,M+1個の
 f_N( ... f_2( f_1(1) ) ... )
の値を調べた.
M+1個の値の最大値を最小値を求める問題.
50点 : Nは1000以下,Mは1000以下.
100点 : Nは10^12以下,Mは10^5以下.

解法

まず,Nが大きいので座標圧縮する.使う箱はたかだかM個.
f_2 * f_1などの合成関数はすべて a * x + b の形で書ける.
セグメントツリーのように,各区間のaとbの値を覚えておけばパラメータの変更と値の計算がlog M程度でできる.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

void intIntSort(ll d[],ll m[],int s){ll i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

ll ind[200000], val[200000], vv[200000];
ll p[200000]; double a[200000], b[200000];

double x[2000000], y[2000000];

void get(int a,int b,int node,double *X, double *Y){
  *X = x[0];
  *Y = y[0];
}

void change(int a,int b,int c,double X,double Y,int node){
  int sz = b-a;
  int n1 = node*2+1, n2 = node*2+2;

  if(c < a || c >= b) return;

  if(sz==1){
    x[node] = X;
    y[node] = Y;
    return;
  }

  change(a, a+sz/2, c, X, Y, n1);
  change(a+sz/2, b, c, X, Y, n2);

  x[node] = x[n1] * x[n2];
  y[node] = x[n2] * y[n1] + y[n2];
}

int main(){
  int i,j,k,l;
  ll N; int M, mm;
  double mn = 1, mx = 1;
  double X, Y;

  scanf("%lld%d",&N,&M);
  rep(i,M) scanf("%lld%lf%lf",p+i,a+i,b+i);

  rep(i,M) ind[i] = i, val[i] = p[i];
  intIntSort(val, ind, M);

  rep(i,M) vv[i] = i;
  REP(i,1,M) if(val[i] == val[i-1]) vv[i] = vv[i-1];
  rep(i,M) p[ind[i]] = vv[i];

  rep(i,8*M) x[i] = 1, y[i] = 0;

  mm = 1;
  while(mm < M) mm *= 2;

  rep(i,M){
    change(0,mm,p[i],a[i],b[i],0);
    get(0,mm,0,&X,&Y);
    if(mn > X + Y) mn = X + Y;
    if(mx < X + Y) mx = X + Y;
  }

  printf("%.10f\n%.10f\n",mn,mx);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2327-93f8c2eb
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。