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: 2017年11月18日04時24分51秒
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)

ログイン: