Google Code Jam 2017 Qualification Round A問題
Problem Statement
$N$ 個のパンケーキが一列に並んでいる.
それぞれのパンケーキは最初表(+)か裏(-)のどちらかである.
操作として,連続するちょうど $K$ 個のパンケーキをひっくり返すことができる.
全てのパンケーキを表にすることが可能か不可能かを判定して,可能ならば最小の操作回数を求める問題.
同じ長さ $K$ の区間に対して $2$ 回ひっくり返すことが無意味なので,それぞれの区間に対してひっくり返すかひっくり返さないかのどちらかを行う.
一番左のパンケーキに着目すると,それをひっくり返せる区間は $1$ つしかないので,
とやれば,一番左のパンケーキが表になり,そのパンケーキを取り除いて同じことを考えていく.
最後にパンケーキの数が $K$ 個になったときに,全部が表なら,答えは可能でそれまでひっくり返した回数が最小,そうでないなら答えは不可能.
愚直にシミュレーションしても時間計算量は $O(N^2)$ 程度.
C++に変換後のコードはこちら
{
int test = 0, TEST;
rd(TEST);
while(TEST--){
printf("Case #%d: ", ++test);
fprintf(stderr, "r=%d\n", TEST);
int K;
char S[1111];
int i, c, n, r = 0;
rd(S, K);
n = strlen(S);
S[0..n-1] = (S[0..]=='-')?0:1;
rep(i,n-K+1) if(S[i]==0) S[i..i+K-1] ^= 1, r++;
c = 0;
rep(i,n) c += S[i];
if(c==n) wt(r); else wt("IMPOSSIBLE");
}
}
Current time: 2024年03月29日18時23分12秒
Last modified: 2017年04月14日00時50分12秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2017 GCJ_2017_Qualification_Round
トップページに戻る
Logged in as: unknown user (not login)