問題はともかく、入出力について考えさせられた問題。
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使ってね」と書いてあるんだけどね。