Google Code Jam 2017 Qualification Round A問題 - Oversized Pancake Flipper

Source

Google Code Jam 2017 Qualification Round A問題
Problem Statement

問題概要

$N$ 個のパンケーキが一列に並んでいる.
それぞれのパンケーキは最初表(+)か裏(-)のどちらかである.
操作として,連続するちょうど $K$ 個のパンケーキをひっくり返すことができる.
全てのパンケーキを表にすることが可能か不可能かを判定して,可能ならば最小の操作回数を求める問題.

解法

同じ長さ $K$ の区間に対して $2$ 回ひっくり返すことが無意味なので,それぞれの区間に対してひっくり返すかひっくり返さないかのどちらかを行う.
一番左のパンケーキに着目すると,それをひっくり返せる区間は $1$ つしかないので,

  1. 一番左のパンケーキが表ならば,その区間ではひっくり返さない
  2. 一番左のパンケーキが裏ならば,その区間ではひっくり返す

とやれば,一番左のパンケーキが表になり,そのパンケーキを取り除いて同じことを考えていく.
最後にパンケーキの数が $K$ 個になったときに,全部が表なら,答えは可能でそれまでひっくり返した回数が最小,そうでないなら答えは不可能.
愚直にシミュレーションしても時間計算量は $O(N^2)$ 程度.

cLayversion 20170408-3)のコード

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: 2017年09月22日15時21分35秒
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)

ログイン: