結果

問題 No.3060 Erase Binary Matrix
ユーザー SPD_9X2
提出日時 2024-10-26 22:30:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,493 ms / 2,000 ms
コード長 2,809 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 83,972 KB
最終ジャッジ日時 2025-03-12 00:40:48
合計ジャッジ時間 27,188 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/11516

操作0回か？ を考える

シミュレーション
-> 消せる行・列が消せなくなることはない
消せるようになる行・列のチェックは、O(n+m)でできる
2乗でシミュレーションはできる

基本はシミュレーションでいい
何も消せない時、どの行を消すのが最適か？

消せないとき、全ての行・列に0,1 が共にある
行を3で消したとき、期待されるのは列が消せるようになり、更に行が消えること

連鎖は以下のように進むはず
行を消す。
ある列集合が0で消せるようになる。消す。
ある行集合が1で消せるようになる。消す。
ある列集合が0で消せるようになる・・・

連鎖はどこまで行くのか？

000111
111000
101000
->
111000
101000
->
1
0
なので、コスト1で全部消せる

--------
101010
010101
101010
010101
-> これはコスト2


行・列 自由にを入れ替えてもよい
列は、同じものをマージしてもよい

列をsortする。

0010101
0101010
1010110
0101001


列3個で考えてみる

001
010
011
100
101
110
の6通りが考えられる

3つ削除は必須
すると
01
10 になるので、更に1回で計4回
縦がとにかく消えるのを貪欲に選んでいいとか？


3で消す行は、一気に選んでいいはず
残りの個所が、0回で消えるならばOK

0回で消えるか？を判定できればいい

01
10 がなければOK?
あれば不可能なのはそう。

一緒に残すことはできない行のペアに辺を引く
その中で、最大独立集合を答えればいい
2部グラフになったりしないかな…

bitで見たときに包含関係だけ考えればいいのか

"""

from sys import stdin
from collections import deque

H,W = map(int,stdin.readline().split())

A = [ stdin.readline()[:-1] for i in range(H) ]

lis = [ [] for i in range(H) ]

for i2 in range(H):

    for i1 in range(i2):

        f12 = True
        f21 = True

        for j in range(W):
            if A[i1][j] < A[i2][j]:
                f12 = False
                break

        for j in range(W):
            if A[i1][j] > A[i2][j]:
                f21 = False
                break

        if f12 and f21:
            lis[i1].append(i2)
        elif f12:
            lis[i1].append(i2)
        elif f21:
            lis[i2].append(i1)

inlis = [0] * H
for i1 in range(H):
    for i2 in lis[i1]:
        inlis[i2] += 1

q = deque([])
dp = [1] * H

for i1 in range(H):
    if inlis[i1] == 0:
        q.append(i1)

while q:
    i1 = q.popleft()
    for i2 in lis[i1]:
        dp[i2] = max(dp[i2] , dp[i1] + 1)
        inlis[i2] -= 1
        if inlis[i2] == 0:
            q.append(i2)

print (H - max(dp))
0