063 - Monochromatic Subgrid（★4）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/26
• 結果：解けた
• 時間： 1時間ぐらい

考えたこと

• DPとかを使うのかと思ったけど、 愚直にやればできそうな気がした。
• 8行分のどれを使うかは全パターン列挙しても256通り。
• 選択した行について、列が同じ数字になっているものを数えれば良さそう

公式解説

https://twitter.com/e869120/status/1403121388773249024/photo/1

解説を読んだふりかえり

• 変な制約、状態数が少ないものは全探索というのが定石なもよう。
• その点には気がつけた気がする。
• 実装が遅かったり、計算量見積もりが適当だったのは良くなかった。

ソース

import itertools
# from collections import defaultdict
from collections import Counter
H, W = [int(x) for x in input().split()]
P = []
for _ in range(H):
    l = [int(x) for x in input().split()]
    P.append(l)

ans = 0
for i in range(1<<H):
    # Pから行を抜粋したのがP2
    ci = [1 if i&(1<<j) else 0 for j in range(H)]
    P2 = list(itertools.compress(P, ci))
 
    # P2の列を順番に各列みて、すべて同じ数値であるかを求める
    counter = Counter()
    for c in range(W):
        L = [P2[r][c] for r in range(len(P2))]
        S = set(L)
        if len(S)==1:
            n = S.pop()
            counter.update([n])
    # 同じ数値の場合は、面積を求めてみて、更新できればする
    if len(counter.most_common()) != 0:
        v, cnt = counter.most_common()[0]
        ans = max(ans, cnt * len(P2))
    
print(ans)