C++で解く！チップ移動の最小コストを求めるアルゴリズム

いくつかのチップが与えられ、i番目のチップは現在、位置 chips[i] に置かれています。次の2種類の操作を、任意のチップに対して何度でも（0回でも可）実行できます。

• i番目のチップを左右どちらかの方向に2単位移動する（コスト0）
• i番目のチップを左右どちらかの方向に1単位移動する（コスト1）

すべてのチップを同じ位置に集めるために必要な最小コストを求めてください。最終的な位置はどこでも構いません。例えば、チップの初期配列が [2,2,2,3,3] の場合、出力は 2 になります。4番目と5番目のチップを位置2へ移動させる際にそれぞれコスト1がかかるため、合計の最小コストは 2 となります。

解法のアプローチ

この問題の鍵となるのは「偶奇性（パリティ）」です。2単位の移動はコスト0で行えるため、偶数位置にあるチップは他のどんな偶数位置へでも無料で移動できます。奇数位置のチップについても同様です。つまり、コストが発生するのは「偶数位置から奇数位置へ」、あるいはその逆の移動だけなのです。

そこで、以下の手順で解きます。

• odd := 0、even := 0 として初期化する
• 配列の先頭から末尾までループする
  • chips[i] が奇数なら odd をインクリメントし、そうでなければ even をインクリメントする
• odd と even の小さい方を返す

C++の実装例

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int odd = 0;
        int even = 0;
        for(int i = 0; i < chips.size(); i++){
            if(chips[i] & 1) odd++;
            else even++;
        }
        return min(odd, even);
    }
};
main(){
    Solution ob;
    vector<int> v1 = {2,2,2,3,3};
    cout << ob.minCostToMoveChips(v1);
}

入力

[2,2,2,3,3]

出力

2