2014年04月13日07時03分33秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

TopCoderOpen Algorithm 2014 Round 1A HARD - EllysLamps

Source

TopCoderOpen Algorithm 2014 Round 1A HARD (1000pt)
Problem Statement

問題概要

$N$ 個の電球と，$N$ 個のスイッチがある．
最初各電球が付いている（$\verb|Y|$）か付いていない（$\verb|N|$）かが与えられる．
スイッチ $k$ を押すと，以下の $4$ つのどれかが起こる．（何回押しても同じことが起こる）

  1. 電球 $k$ のON/OFFが反転する
  2. 電球 $k$ と $k-1$ のON/OFFが反転する（$k \geq 2$）
  3. 電球 $k$ と $k+1$ のON/OFFが反転する（$k < N$）
  4. 電球 $k$ と $k-1$ と $k+1$ のON/OFFが反転する（$k \geq 2$ かつ $k < N$）

電球をできるだけ消したいが，スイッチが最悪の場合，どうやっても最低でいくつかの電球が付いていることがある．
そのような電球の数を求める問題．

解法

消せないパターンその1は，$\verb|YN|$ または $\verb|NY|$ で，それぞれのスイッチが，$2$ つの電球を同時に切り替える場合．
消せないパターンその2は，$\verb|YYY|$ で，真ん中のスイッチは $3$ つの電球全てと，左右のスイッチは真ん中の電球とも連動しているという場合も，1つは電球がついたままになる．
パターン2は $\verb|NNY|$ とかもそうだが，パターン1に帰着させた場合のほうが，最終的な付いている電球の数が多くなるので考えない．
同様に，端のスイッチが範囲外の電球と連動している場合も，考えなくて良い．
上に挙げた2パターンが最大いくつ含まれるかをDPで数えた．Greedyに数えても良い．

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

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

class EllysLamps {
public:
int getMin(string lamps) {
  int i, n;
  int dp[60];

  n = lamps.size();
  dp[0] = 0;
  rep(i,n){
    dp[i+1] = dp[i];
    if(i-1 >= 0){
      if(lamps[i-1] != lamps[i]) dp[i+1] = max(dp[i+1], dp[i-1] + 1);
    }
    if(i-2 >= 0){
      if(lamps[i-2] == 'Y' && lamps[i-1] == 'Y' && lamps[i] == 'Y') dp[i+1] = max(dp[i+1], dp[i-2] + 1);
    }
  }

  return dp[n];
}

}

Current time: 2024年04月20日18時00分37秒
Last modified: 2014年04月13日07時03分33秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_1A
トップページに戻る

Logged in as: unknown user (not login)

ログイン：