AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の63問目である「Monochromatic Subgrid（★4）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【063 – Monochromatic Subgrid（★4）】
考察
はじめに、すべての数字ごとに条件を満たすか確認するアプローチを考えるかもしれませんが、これは数字の数×探索範囲=O(HWHW)となり、TLEになってしまいます。
そこで、行と列の組み合わせを全探索するアプローチを採用します。特に、H の制約が8と小さいため、bit全探索が可能です。bit全探索を用いることで、行の組み合わせを効率的に全探索することができます。
手順
- 行の組み合わせを全探索
- 各列での値の確認
- 出現回数のカウント
- 最大部分グリッドの大きさの計算
1. 行の全探索
まず、行の全ての組み合わせをbit全探索で求めます。
for bit in itertools.product([0, 1], repeat=H):
use_num = [i for i in range(H) if bit[i] == 1]ここで、use_num は選択された行のインデックスが格納されます。
2. 同じ値が存在する列の確認
次に、選択された行の中で、各列が同じ値を持つかどうかを確認します。
for j in range(W):
value = box[use_num[0]][j]
if all(box[u][j] == value for u in use_num):ここで、value は選択された行の最初の行の値を示しています。そして、all 関数を使用して、選択されたすべての行でその値が一致するかどうかを確認しています。
3. 出現回数のカウント
各列で一致した値の出現回数をカウントします。
if value not in count:
count[value] = 1
else:
count[value] += 14. 最大部分グリッドの大きさの計算
最後に、これまでにカウントした中で最も頻繁に出現した値の回数と、選択した行の数を掛け合わせて、最大の部分グリッドの大きさを計算します。
freq_max = max(count.values(), default=0)
ans = max(ans, len(use_num) * freq_max)典型解法：工夫した全探索
コード
# bit全探索
import itertools
H, W = map(int, input().split())
box = []
for i in range(H):
P = list(map(int, input().split()))
box.append(P)
ans = 0
# 行の組み合わせを全探索
for bit in itertools.product([0, 1], repeat=H):
use_num = [i for i in range(H) if bit[i] == 1]
# 選択された行がない場合はスキップ
if not use_num:
continue
count = {}
# 列に関しても同様に全探索
for j in range(W):
# 最初の行のj列目の値を取得
value = box[use_num[0]][j]
# すべての行でj列目の値が同じかどうかを判定
if all(box[u][j] == value for u in use_num):
#選択された各行に対して、各列の数値が一致するかを確認します。一致する場合、その値の出現回数をカウント
#各列で一致した値の出現回数をカウント
if value not in count:
count[value] = 1
else:
count[value] += 1
freq_max = 0#最も頻繁に出現した値の回数
for key in count:
freq_max = max(freq_max, count[key])
# 選択した行の数と、すべての値が同じであった列の数を掛け合わせて部分グリッドの大きさを計算
ans = max(ans, len(use_num) * freq_max)
print(ans)
コメント