Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #107 DIV1 C問題/DIV2 E問題 - Smart Cheater (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 C問題 (1000pt)
Codeforces Round #107 DIV2 E問題 (3000pt)
Problem description

問題概要

電車の車長が,乗客(m人,300000以下)とグルで不正して,儲かるお金の期待値を最大化した時の期待値を求める問題.
各駅と駅の間で,チケットチェックが入る確率が与えられる.その時,その区間のチケットを持ってないとcだけ罰金を払うことになる.
駅の数はn.(150000以下)
乗客が乗る部分の連続する一部区間のチケットを売らないで,儲かる利益は車長と乗客とで等しく分配する.
とかだが,問題文が曖昧で,問題背景も微妙なので,問題を定式化した後のものを書く.

n個の整数,x[i]が与えられる.(i = 1~n)
n-1個の整数,p[i]が与えられる.(0以上100以下)
n-1個の実数,g[i] = x[i+1] - x[i] - 2*c*p[i]/100 で定義する.
m個の整数のペア,a, bが与えられる.(1 ≤ a < b ≤ n)
各整数のペアに対して,
 a ≤ c ≤ d ≤ bなるc, dのうち,Σ[k=c..d-1] g[k]の最大値を求める.(c=dなら和は0)
その最大値の和 / 2を求める問題.

解法

つまりは,ある区間の連続する部分和の最大値を高速に求める問題になる.
segment treeを使う.
そのままやるなら,seg treeの各区間では,左端から連続する部分の最大値,右端から連続する部分の最大値,(端からじゃなくて良い) 連続する部分の最大値を計算する.
最初に,累積和 s[k] = g[1] + g[2] + ... + g[k] を計算しておいて,それを用いるなら,s[j] - s[i] (j ≥ i) の最大値を高速に求める問題になる.
その場合は,seg treeの各区間では,最小値,最大値,その区間でのs[j] - s[i] (j ≥ i)の最大値を計算すれば良い.

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)

int dist[900000];
double p[900000];
double gain[900000], sum[900000];

double mn[900000], mx[900000], sa[900000];

void seg_tree_set(int left, int right, int n){
  int n1, n2;
  int sz = right - left;

  if(sz==1){
    mn[n] = mx[n] = sum[left];
    sa[n] = 0;
    return;
  }

  n1 = n * 2 + 1;
  n2 = n * 2 + 2;
  seg_tree_set(left, left+sz/2, n1);
  seg_tree_set(left+sz/2, right, n2);

  mn[n] = mn[n1]; if(mn[n] > mn[n2]) mn[n] = mn[n2];
  mx[n] = mx[n1]; if(mx[n] < mx[n2]) mx[n] = mx[n2];
  sa[n] = sa[n1]; if(sa[n] < sa[n2]) sa[n] = sa[n2];
  if(sa[n] < mx[n2] - mn[n1]) sa[n] = mx[n2] - mn[n1];
}

void seg_tree_calc(int a, int b, int left, int right, int n, double *mn3, double *mx3, double *sa3){
  int n1, n2;
  int sz = right - left;
  double mn1, mn2, mx1, mx2, sa1, sa2;

  if(a < left) a = left;
  if(b > right) b = right;
  if(b-a <= 0){
    *mn3 = 1e100;
    *mx3 = -1e100;
    *sa3 = -1e100;
    return;
  }

  if(a==left && b==right){
    *mn3 = mn[n];
    *mx3 = mx[n];
    *sa3 = sa[n];
    return;
  }

  n1 = n * 2 + 1;
  n2 = n * 2 + 2;
  seg_tree_calc(a, b, left, left+sz/2,  n1, &mn1, &mx1, &sa1);
  seg_tree_calc(a, b, left+sz/2, right, n2, &mn2, &mx2, &sa2);

  *mn3 = mn1; if(*mn3 > mn2) *mn3 = mn2;
  *mx3 = mx1; if(*mx3 < mx2) *mx3 = mx2;
  *sa3 = sa1; if(*sa3 < sa2) *sa3 = sa2;
  if(*sa3 < mx2 - mn1) *sa3 = mx2 - mn1;
}

int main(){
  int i,j,k,l,m,n,c;
  int a, b;
  int num, node;
  double res, mn, mx, sa;

  while(scanf("%d%d%d",&n,&m,&c)==3){
    res = 0;
    rep(i,n) scanf("%d",dist+i);
    rep(i,n-1) scanf("%d",&k), p[i] = k / 100.0;

    num = 1;
    while(num < n+1) num *= 2;
    node = num * 2 - 1;

    rep(i,num) gain[i] = 0;
    rep(i,n-1) gain[i] = dist[i+1] - dist[i] - p[i]*c*2;

    sum[0] = 0;
    rep(i,num) sum[i+1] = sum[i] + gain[i];

    seg_tree_set(0, num, 0);

    while(m--){
      scanf("%d%d",&a,&b);
      seg_tree_calc(a-1, b, 0, num, 0, &mn, &mx, &sa);
      res += sa;
    }

    res /= 2;
    printf("%.10f\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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