kmjp's blog

競技プログラミング参加記です

Codeforces #221 Div1. B. Maximum Submatrix 2

問題はともかく、入出力について考えさせられた問題。
http://codeforces.com/contest/375/problem/B

問題

0と1からなるNxM要素の行列が与えられる。
この行列に対し行同士の入れ替えが可能である場合、この行列から1のみで構成される長方形領域のうち最大の要素数を答えよ。

解法

まず、行列の各行について、長方形の左端を各列においた場合に何個連続1が連続するかをカウントする。この処理はO(NM)。

次に、長方形の左端を各列においた場合、上記連続する1の数を各行の分配列にいれて昇順ソートする。
この配列をV[i]とすると、V[i]>=xとなる要素がy個あれば、行入れ替えによりx*yの長方形が作れることになる。
よってxをVの各要素にした場合、x=V[i]、y=(M-i)と考えてmax(V[i]*(M-i))が答え。
以下のコードは行数分配列に入れてソートするのでO(NM logM)かかるが、ソート処理を行わない方法もあり、O(NM)で完了できるようだ。
今回の時間制限ではO(NM logM)でも問題ない。

ここで入力について問題がある。
今回の問題はN,M<=5000のため、最大ケースで25MBもの文字列を読まないといけない。
この場合cinでは読み込みだけでTLEする可能性がある。Cygwinだと13秒もかかった。
そのため自分は本番はcinをやめgetsを使って回避した。

cinの遅さは、ios::sync_with_stdio(false);を事前に実行しておくことで回避できるようだ。
この場合最大ケースも0.6秒で実行完了し、CFのサーバでも1秒を切れた。

int H,W;
string S[5010];
int mat[5001][5001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		for(x=W-1;x>=0;x--) {
			if(S[y][x]=='0') mat[y][x]=0;
			else mat[y][x]=mat[y][x+1] + 1;
		}
	}
	int ret=0;
	FOR(x,W) {
		vector<int> V;
		FOR(y,H) if(mat[y][x]>0) V.push_back(mat[y][x]);
		sort(V.begin(),V.end());
		FOR(i,V.size()) ret=max(ret,V[i]*((int)V.size()-i));
	}
	_P("%d\n",ret);
}

まとめ

問題の内容はともかく、cinのドタバタが残念な問題。
コンテストによっては「cinは遅いのでscanf使ってね」と書いてあるんだけどね。