TopCoder SRM616 DIV1 EASY - WakingUp

Source

TopCoder SRM616 DIV1 EASY (250pt)
Problem Statement

問題概要

最初 $t=0$,睡眠レベルは未知の整数 $s$ で,最終的に目覚めることができる最大の $s$ を求める問題.(無限大ならそれを指摘する)
目覚まし時計が $N$ 個あり,$k$ 番目の時計は,時刻 $S_k, S_k+P_k, S_k+2P_k, \ldots$ と $P_k$ ごとにうるささ $V_k$ で鳴る.
各時刻 $t \geq 1$ では,

  1. $T$ だけ睡眠レベルが増える
  2. その時刻になっている時計があれば,なっている時計のうるささの和だけ睡眠レベルが減る

と睡眠レベルが変化する.
また,睡眠レベルが $0$ 以下になった瞬間に目が覚める.(時刻 $t=0$ で目覚めることも可能)

解法

${\rm LCM}(1,2,\ldots,10) = 2520$ より,時刻 $t$ と時刻 $t+2520$ には同じことが起こる.
よって,時間 $2520$ ステップシミュレーションして,睡眠レベルが減るなら,どんな初期睡眠レベルでもいずれ目覚める.
そうでなければ,最初の $2520$ ステップの中で,最も睡眠レベルが減るときに目覚めるようにすれば,初期睡眠レベルが最大となる.

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class WakingUp {
public:
int maxSleepiness(vector <int> period, vector <int> start, vector <int> volume, int D) {
  int i, j, n;
  int dp[2521];
  int res;

  n = period.size();

  dp[0] = 0;
  REP(i,1,2521){
    dp[i] = dp[i-1] + D;
    rep(j,n) if( (i-start[j])%period[j]==0 ){
      dp[i] -= volume[j];
    }
  }

  if(dp[2520] < dp[0]) return -1;

  res = 0;
  rep(i,2521) res = max(res, -dp[i]);
  return res;
}

}

Current time: 2017年11月19日12時16分19秒
Last modified: 2014年04月11日09時46分27秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM616 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: