Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #219 DIV1 C問題/DIV2 E問題 - Watching Fireworks is Fun (この記事を編集する[管理者用])

Source

Codeforces Round #219 DIV1 C問題 (1500pt)
Codeforces Round #219 DIV2 E問題 (2500pt)
Problem description

問題概要

一直線上に $N$ 個の区画($1,2,\ldots,N$)があり,隣り合う各区画間の距離は $1$ である.
$M$ 回だけ花火が上がる.
$k$ 回目の花火が上がる場所は $A_k$ で,時刻は $T_k$ である.
その花火が上がった時に区画 $x$ にいたなら $B_k - |A_k - x|$ だけ満足度が得られる.(負もありうる)
単位時間あたり $D$ だけ移動できるとして,得られる満足度の和の最大値を求める問題.
ただし,花火の上がる時間には,区画のどこかにいなければいけない.また,花火は同時に複数上がる場合がある.
$1 \leq N \leq 150000\ (1.5 \times 10^5)$
$1 \leq M \leq 300$
$1 \leq D \leq N$
$1 \leq A_k \leq N$
$1 \leq B_k \leq 10^9$
$1 \leq T_1 \leq T_2 \leq \cdots \leq T_M \leq 10^9$

解法

DPする.状態は 最後に上がった花火と最後に花火を見た場所 にして それまでの満足度の最大値 を計算する.
その際,状態を更新するのにある区間にある最大値というのが必要になる.
スライド最小値や,Range Minimum Queryを使う.

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 MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

#define ll long long
#define READER_BUF_SIZE 65536
#define myIsDigit(x) ('0'<=(x) && (x)<='9')
#define myIsSpace(x) ((x)==' ' || (x)=='\t' || (x)=='\n' || (x)=='\r')

int reader_pt = READER_BUF_SIZE;
char reader_buf[READER_BUF_SIZE];

int reader_nonneg_int(){
  int r;

  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(myIsDigit(reader_buf[reader_pt])) break;
    reader_pt++;
  }
  r = reader_buf[reader_pt++] - '0';
  for(;;){
    if(reader_pt==READER_BUF_SIZE) reader_pt = 0, fread(reader_buf, READER_BUF_SIZE, sizeof(char), stdin);
    if(!myIsDigit(reader_buf[reader_pt])) break;
    r = r*10 + (reader_buf[reader_pt++]-'0');
  }
  reader_pt++;

  return r;
}


void doublingRMQBuild(ll arr[], int n, int res[]){
  int i, k, hf;

  rep(i,n) res[i] = i;
  for(k=1;;k++){
    hf = (1<<(k-1)); if(hf >= n) break;
    rep(i,n){
      res[n*k+i] = res[n*(k-1)+i];
      if(i+hf < n && arr[res[n*k+i]] < arr[res[n*(k-1)+i+hf]]) res[n*k+i] = res[n*(k-1)+i+hf];
    }
  }
}

int doublingRMQQuery(ll arr[], int n, int rmq[], int a, int b){
  int dep, wid = b-a+1, A, B;
  for(dep=0;(1<<(dep+1))<=wid;dep++);
  A = rmq[n*dep+a];
  B = rmq[n*dep+b-(1<<dep)+1];
  if(arr[A] < arr[B]) A = B;
  return A;
}

ll ab(ll x){ if(x<0) return -x; return x; }

int main(){
  ll n, m, d;
  ll a[333], b[333], t[333];

  int i,j,k,l;
  ll left, right;
  ll res;
  static ll mx[200000], nx[200000];
  static int rmq[5000000];


  n = reader_nonneg_int();
  m = reader_nonneg_int();
  d = reader_nonneg_int();
  rep(i,m){
    a[i] = reader_nonneg_int() - 1;
    b[i] = reader_nonneg_int();
    t[i] = reader_nonneg_int();
  }

  rep(i,n) mx[i] = b[0] - ab(a[0] - i);
  REP(k,1,m){
    doublingRMQBuild(mx, n, rmq);
    rep(i,n){
      left  = i - d * (t[k] - t[k-1]);
      right = i + d * (t[k] - t[k-1]);
      if(left < 0) left = 0;
      if(right >= n) right = n-1;

      j = doublingRMQQuery(mx, n, rmq, left, right);
      nx[i] = mx[j] + b[k] - ab(a[k] - i);
    }
    rep(i,n) mx[i] = nx[i];
  }

  res = mx[0];
  REP(i,1,n) res = MAX(res, mx[i]);

  printf("%I64d\n",res);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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