The Water Bowls POJ3185

投稿日：2022/12/24 更新日:2022/12/24

問題

20個の水入れがある。それぞれの水入れは飲むのに適した状態と適さない状態がある。20個の水入れを全て適した状態にするためにひっくり返していく。しかし、ひっくり返す際1つだけでなく左右に隣接する物もひっくり返してしまう。(合計3つをひっくり返す。端の場合は２つ)

初期値1=適さない状態、0=適切な状態が与えられるので、必要な最小の操作回数をもとめてください。

解法

まず、 $i$ 番目をひっくり返す時、 $i-1$ と $i+1$ もひっくり返されるが、扱いにくいので、言い換えて、 $i$ 番目をひっくり返す時、 $i+1, i+2$ もひっくり返されるとする。

そうすると、 $s_1, s_2, ...$ と状態が並んでいる時、端の $s_1$ を操作する必要があれば、操作し、 $s_2, s_3$ を反転させる。次に $s_2$ を見る、のように端から処理していけば良い。

ただし、一番端は $s_1, s_2, s_3$ の3つを反転させるパターンと、 $s_1, s_2$ の2つを反転させる２パターンがある。そのため、 $s_0$ というダミーを追加し、 $s_0 = 1, 0$ どちらもシミュレーションし、2つのパターンを処理する。

実装

#include <iostream>
#include <vector>
using namespace std;

int flip(vector<bool> undrink){
    int n = undrink.size();
    int count = 0;
    for(int i = 0;i < n-2; ++i){
        if(!undrink[i])continue;
        count++;
        undrink[i] = !undrink[i];
        undrink[i+1] = !undrink[i+1];
        undrink[i+2] = !undrink[i+2];
    }
    if(undrink[n-2]){
        undrink[n-2] = !undrink[n-2];
        undrink[n-1] = !undrink[n-1];
        count++;
    }

    if(undrink[n-1]){
        return 9999;
    }
    return count;
}

void solve(){
    const int n = 20;
    vector<bool> undrink(n+1);
    for(int i = 1;i <= n; ++i){
        int x;
        cin >> x;
        if(x == 1){
            undrink[i] = true;
        }
    }

    int ans = flip(undrink);
    undrink[0] = true;
    ans = min(ans, flip(undrink));

    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
    return 0;
}