TopCoderOpen Algorithm 2014 Round 1A HARD (1000pt)
Problem Statement
$N$ 個の電球と,$N$ 個のスイッチがある.
最初各電球が付いている($\verb|Y|$)か付いていない($\verb|N|$)かが与えられる.
スイッチ $k$ を押すと,以下の $4$ つのどれかが起こる.(何回押しても同じことが起こる)
電球をできるだけ消したいが,スイッチが最悪の場合,どうやっても最低でいくつかの電球が付いていることがある.
そのような電球の数を求める問題.
消せないパターンその1は,$\verb|YN|$ または $\verb|NY|$ で,それぞれのスイッチが,$2$ つの電球を同時に切り替える場合.
消せないパターンその2は,$\verb|YYY|$ で,真ん中のスイッチは $3$ つの電球全てと,左右のスイッチは真ん中の電球とも連動しているという場合も,1つは電球がついたままになる.
パターン2は $\verb|NNY|$ とかもそうだが,パターン1に帰着させた場合のほうが,最終的な付いている電球の数が多くなるので考えない.
同様に,端のスイッチが範囲外の電球と連動している場合も,考えなくて良い.
上に挙げた2パターンが最大いくつ含まれるかをDPで数えた.Greedyに数えても良い.
// #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日23時14分33秒
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)