保存されている過去のバージョンの一覧

2014年04月11日09時46分27秒
2014年04月11日05時26分46秒

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: 2024年04月20日18時48分17秒
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)

ログイン：