JOI2008予選5 おせんべい

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e

この問題は全探索を用いて解くことができます。

方針

  • 裏返しによって煎餅は反転するだけですので、ある一連の操作があったとして、その操作の順番を入れ替えても結果は変わりません。
  • ある特定の列や行を二回裏返すと当然元に戻ります。つまり、ある特定の列や行を二回以上裏返す必要はなく、裏返すか裏返さないかの二択を考えれば良いです。

以上の考察により全探索の計算量はO(2^(R+C))となることがわかります。しかし、これだと今回の制約では間に合いません。

そこで、縦R行の固定を考えます。固定のパターンは2^R通りとなります。縦列が固定されると各行を裏返す返さないを独立に決めることができます。具体的には各行について、裏返した場合と裏返さない場合で良い方を選ぶだけです。

この場合、計算量はO(CR2^R)となり間に合います。

コード

このような全探索をbit全探索と呼びます。Pythonではitertools.productを利用すると良いでしょう。なお、PythonではTLEとなってしまうため、PyPyで提出しました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import product
R, C = map(int,input().split())
lines = []
for r in range(R):
line = list(map(int,input().split()))
lines.append(line)
lines = list(zip(*lines))
ans = 0
for p in product((0,1),repeat=R):
sm = 0
for line in lines:
cnt = 0
for r in range(R):
if p[r] == line[r]:
cnt += 1
sm += max(cnt, R-cnt)
ans = max(ans, sm)
print (ans)

記事情報

  • 投稿日:2020年5月19日
  • 最終更新日:2020年5月19日