読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #345 Div.2 E / Div.1 C - Table Compression

強連結成分分解 DP codeforces

久し振りにRatedなコンテストに出て、div1で2問なんとか解いたけど、遅かったのでレートは微減した
div1は厳しい

問題

Codeforces Round #345 Div.1 C - Table Compression
要素が全て正のN行M列の行列Aが与えられる。これを各行・列の相対的な大小関係が等しい行列のうち、最大の要素が最小となるような行列A'を求めよ。
ここで行列AとA'の各行の相対的な大小関係が等しいとは、Aの要素a_{i,j}と行が同じ要素a_{i,k}と、それに対応するA'の要素a'_{i,j}とa'_{i,k}について、a_{i,j} < a_{i,k} ならば a'_{i,j} < a'_{i,k}、a_{i,j} = a_{i,k}ならば a'_{i,j} = a'_{i,k}、a_{i,j} > a_{i,k} ならば a'_{i,j} > a'_{i,k} が成立することである。(列に関しても同様)

制約

1<= N*M <= 10^6
1<= a_{i,j} <= 10^9

解法

まずAの各行・列に対して、相対的な大小関係を有向グラフを用いて表す。
つまり、行に対しては、a_{i,j} < a_{i,k}ならば頂点(i,j)から(i,k)に辺をはり、a_{i,j} = a_{i,k}ならば、頂点(i,j)と(i,k)について双方向に辺をはる。列に関しても同様に辺をはる。
そうすると、A'において値が同じにならなければいけない頂点集合はグラフにおいて強連結成分となる。よって、強連結成分分解をして、DAGを作る。
このDAG上において、次のDPを行う。
dp[i] := (DAGのi番目の頂点に対応する行列の要素の値) として、
dp[i] = 1 (頂点iに親が存在しない場合)
dp[i] = max{dp[par_v] + 1 | 頂点vはDAG上で頂点iであり、かつpar_v→vという枝があり、かつparはDAG上で頂点iではない} (頂点iに親が存在する場合)
これを計算してa'_{i,j} = dp[頂点(i,j)に対応するDAG上の頂点]とすればA'が求まる。

ただ、各行・列の任意の要素に対して、大小関係を調べて辺をはると、O(NM^2 + MN^2) = O(MN(M+N))かかるので間に合わないが、これは、各行・列をソートし、ソート済みの列の隣り合う要素(つまり行iについてはa_{i,j}とa_{i,j+1})に対して大小関係を調べればOKである。この場合はO(N MlogM + M NlogN) = O(MNlogMN)なので間に合う。

計算量

最初のグラフを構成する部分は上で説明したようにO(MNlogMN)
作られたグラフは頂点数|V|=NM、枝数|E|=N(M-1)+M(N-1)なので、強連結成分分解はO(|V|+|E|) = O(MN)
DAG上のDPは、強連結成分分解を求めるときに使った逆辺を用いると、結局は各頂点・枝について一度ずつしか見ないのでO(MN)
よって、全体ではO(MNlogMN) + O(MN) + O(MN) = O(MNlogMN)

今回はTLが4秒なので、今回のように多少定数倍が大きくても通る。(ただcinとcoutを使うとTLEするかも)

コード


感想

・強連結成分分解すれば解けるということは問題みて割とすぐに思いついたけど、O(NM^2 + MN^2)でグラフを構成する方法しか思いつかなかったので時間内には解けなかった
・まあ強連結成分分解を実装したことがなかったから解ってても間に合わなかった可能性が高いけども
・最初、値が1になるところ1箇所だけだと勘違いしていたので、dpを0で初期化していてWAを出していた


・最大ケースを手元で実行すると再帰回数が最悪10^6になってsegmentation faultしたが、ジャッジ側では問題がなかった(Codeforces側ではコンパイラオプションでスタックサイズを限界まで拡張しているらしい。参考: About the programming languages - Codeforces)
・強連結成分分解のDFSをstackで書きなおしたら遅くなった...