Namaran

Code daily. Without assist.

2026-11-09

flip_grid.cpp

int max_ones(const std::vector<std::string>& rows) {
}

0 と 1 だけからなる同じ長さの文字列を何行か並べた表 rows があります。1回の操作では、どれか1行か、どれか1列を選び、その中の文字をすべて反転します(0 と 1 を入れ替えます)。操作を好きな順に何回でも行ってよいとき、表に含まれる 1 の個数として作れる最大値を返す max_ones を書いてください。行は1行以上10行以下、列は1列以上10000列以下です。

入力例 1

max_ones({"101", "010"})

出力例 1

6

入力例 2

max_ones({"11", "10"})

出力例 2

3

入力例 3

max_ones({"0110"})

出力例 3

4
Reference

Reference

#include <algorithm>
#include <print>
#include <string>
#include <vector>

int max_ones(const std::vector<std::string>& rows) {
    const int h = static_cast<int>(rows.size());
    const std::size_t w = rows[0].size();
    int best = 0;
    for (int flip = 0; flip < (1 << h); ++flip) {
        int total = 0;
        for (std::size_t j = 0; j < w; ++j) {
            int ones = 0;
            for (int i = 0; i < h; ++i) {
                ones += (rows[i][j] == '1') != ((flip >> i) & 1);
            }
            total += std::max(ones, h - ones);
        }
        best = std::max(best, total);
    }
    return best;
}

同じ行や列を2回反転すると元に戻り、反転の順番を入れ替えても結果は変わりません。どのマスも、その行と列が反転された回数の合計が奇数か偶数かだけで決まるからです。そのため、各行と各列について決めるのは「1回反転するかしないか」だけです。とはいえ、行と列の組み合わせをまとめて試すと、列が10000本あれば210010 通りになり、試し切れません。

行の反転を先に決めてしまうと、残りは列ごとの問題に分かれます。列を反転してもほかの列のマスは変わらないので、各列は互いに関係なく、良いほうを選べます。列の中に 1 が ones 個あれば、反転しなければ ones 個、反転すれば h - ones 個なので、その列から得られるのは std::max(ones, h - ones) 個です。行の反転の決め方は、行の集合の部分集合なので、高々210 = 1024通りです。参考実装では整数 flip の i ビット目が1なら i 行目を反転したとみなし、全部の flip について列ごとの最大を足し、その最大を返します。反転後のマスが 1 になるのは、元の文字が 1 であることと行を反転したことの一方だけが成り立つときなので、(rows[i][j] == '1') != ((flip >> i) & 1) で数えます。計算は1024 × 10 × 10000回ほどの比較で終わります。これは参考実装で、唯一の正解ではありません。

入力例1では、2行目を反転すると表は "101" が2行になり、各列は2マスとも同じ文字になるので、0 の列を反転して6マスすべてを 1 にできます。入力例2では、1列目は2マスが同じ文字、2列目は違う文字です。列を反転しても2マスが同じかどうかは変わらず、行を反転すると全部の列で同時に入れ替わるので、どちらかの列には必ず 0 が1つ残り、最大は3です。行が1行だけの入力例3では、列ごとに反転するかどうかを選べるので、4マスすべてが 1 になります。