063.md

063 - Monochromatic Subgrid (★4)

解答

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm> // std::max(), std::max_element()

int main()
{
	// 縦 H 行, 横 W 列
	int H, W;
	std::cin >> H >> W;

	std::vector<std::vector<int>> P(H, std::vector<int>(W));
	for (auto& row : P)
	{
		for (auto& elem : row)
		{
			std::cin >> elem;
		}
	}

	int answer = 0;

	// 行の選び方を bit 全探索
	for (int i = 1; i < (1 << H); ++i)
	{
		// 列内がすべて同じ値である場合の記録
		// <値, 列数>
		std::unordered_map<int, int> map;

		// 各列について
		for (int x = 0; x < W; ++x)
		{
			// 選んだ最初の行の値
			int value = -1;
			
			// すべての行の値が同じであるか
			bool ok = true;

			for (int y = 0; y < H; ++y)
			{
				if ((i & (1 << y)) == 0) // 選んでいない行はスキップ
				{
					continue;
				}

				if (value == -1) // 最初の行なら
				{
					value = P[y][x];
				}
				else if (value != P[y][x])
				{
					ok = false;
					break;
				}
			}

			// 列内がすべて同じ値である場合, その値を記録する
			if (ok)
			{
				++map[value];
			}
		}

		// 列内がすべて同じ値である列があれば
		if (!map.empty())
		{
			// 最も頻出する値の列数を求める
			const int modeCols = std::max_element(map.begin(), map.end(), [](const auto& a, const auto& b)
				{
					return (a.second < b.second);
				})->second;

			// 何行選んだか
			int rows = 0;
			for (int y = 0; y < H; ++y)
			{
				if ((i & (1 << y)) != 0)
				{
					++rows;
				}
			}

			// 部分グリッドの大きさを求め, これまでの記録を超えていたら更新
			answer = std::max(answer, (modeCols * rows));
		}
	}

	// 解答を出力
	std::cout << answer << '\n';
}