はまやんはまやんはまやん

hamayanhamayan's blog

Revised Russian Roulette [Week of Code 36 B]

https://www.hackerrank.com/contests/w36/challenges/revised-russian-roulette

N個のドアがあり、開いているか閉まっている。
閉まっているドアを以下のルールで開けていく時に、全てのドアを開けるのに必要な最小回数と最大回数を答えよ。

  • あるドアを開ける時に次のドアが閉まっていたら、次のドアも開ける
  • あるドアを開ける時に次のドアが開いていたら、なにもしない

解法

最大回数は1を数えればいい。
後ろの閉まっているドアから順番にあけていけば最大回数で開けられる。
最小回数は前から順番にあけていけばいい。
なるべく前から開けることで、なるべく次のドアを開けることができる。

int N, A[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    int ma = 0;
    rep(i, 0, N) if (A[i]) ma++;

    int mi = 0;
    rep(i, 0, N) {
        if (A[i]) {
            mi++;
            A[i + 1] = 0;
        }
    }

    printf("%d %d\n", mi, ma);
}