グリッド内の偶数セルの数を最大化するための操作回数を求めるC++プログラム

問題の概要

ここでは、h × w のサイズを持つグリッドが与えられ、各セルにはそれぞれ固有の値が割り当てられているものとします。この課題のゴールは、偶数の値を持つセルの数をできるだけ多くすることです。

そのために使える操作は次のとおりです。まだ一度も選択していないセルを1つ選び、そのセルの値を1減らし、現在のセルと上下左右で隣接する別のセルの値を1増やします。そして、実行した操作の総数と、各操作における「値を減らすセル」および「値を増やすセル」の座標を出力します。

出力は以下の形式で行います。

• 操作の回数

• 1回目：（値を減らすセルの位置） - （値を増やすセルの位置）

  ……

• n回目：（値を減らすセルの位置） - （値を増やすセルの位置）

例として、入力が h = 3、w = 3、grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}} の場合、出力は次のようになります。

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)

解法のポイント（貪欲法）

この問題は貪欲法を使って効率よく解くことができます。考え方はシンプルで、次のような方針に基づいています。

• 各行を左から右へ走査し、奇数のセルを見つけたら、そのセルの値を1減らして、余った「1」を右隣のセルへ渡します（ただし最終列を除きます）。

• すべての行の処理が終わったら、最終列（w-1列目）に対して上から下へ同様の処理を適用し、奇数のセルから下のセルへ「1」を渡します。

• この方法により、可能な限り多くのセルが偶数化され、すべての操作はグリッド内の隣接セル間で完結します。

手順

この方針に沿って、以下のステップで処理を進めます。

タプルを格納する新しい配列 result を定義する
i := 0 から i < h の間、i を 1 ずつ増やしながら繰り返す：
    tp := 0
    j := 0 から j < w の間、j を 1 ずつ増やしながら繰り返す：
        if tp > 0 ならば：
            result の末尾にタプル(i, j - 1, i, j)を挿入する
            grid[i, j] := grid[i, j] + tp
        if grid[i, j] mod 2 == 1 かつ j < w-1 ならば：
            grid[i, j] := grid[i, j] - 1
            tp := 1
        そうでなければ
            tp := 0
tp := 0
i := 0 から i < h の間、i を 1 ずつ増やしながら繰り返す：
    if tp > 0 ならば：
        result の末尾にタプル(i - 1, w - 1, i, w - 1)を挿入する
        grid[i, w - 1] := grid[i, w - 1] + tp
    if grid[i, w - 1] mod 2 == 1 ならば：
        grid[i, w - 1] := grid[i, w - 1] - 1
        tp := 1
    そうでなければ
        tp := 0
print(result のサイズ)
i := 0 から i < result のサイズ の間、i を 1 ずつ増やしながら繰り返す：
    print('(' + result[i] の第1値 + ', ' + result[i] の第2値 + ') - (' + result[i] の第3値 + ', ' + result[i] の第4値 + ')')

C++実装例

より理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(int h, int w, vector<vector<int>> grid){
    vector<tuple<int,int,int,int>> result;
    for(int i = 0; i < h; i++){
        int tp = 0;
        for(int j = 0; j < w; j++){
            if(tp > 0){
                result.push_back(make_tuple(i, j-1, i, j));
                grid[i][j] += tp;
            }
            if(grid[i][j]%2 == 1 && j < w-1){
                grid[i][j] -= 1;
                tp = 1;
            }
            else
                tp = 0;
        }
    }
    int tp = 0;
    for(int i = 0; i < h; i++){
        if(tp > 0){
            result.push_back(make_tuple(i-1, w-1, i, w-1));
            grid[i][w-1] += tp;
        }
        if(grid[i][w-1]%2 == 1){
            grid[i][w-1] -= 1;
            tp = 1;
        }
        else
            tp = 0;
    }
    cout << (int)result.size() << endl;
    for(int i = 0; i < (int)result.size(); i++){
        cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i])
        << ")" << " - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")";
        cout << '\n';
    }
}
int main() {
    int h = 3, w = 3 ;
    vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}};
    solve(h, w, grid);
    return 0;
}

計算量

グリッドの全セルを高々2回走査するだけでよいため、時間計算量は O(h × w) となり、非常に効率的です。また、記録される操作数も最大でも O(h × w) 程度に収まります。

入力

3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}

出力

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)