AtCoderログ：0070 - ABC 213 C

問題

問題文

$H$ 行 $W$ 列の格子状に $HW$ 枚のカードが並べられています。$i=1,\cdots,N$
について、上から $A_i$ 行目、左から $B_i$ 列目にあるカードには数 $i$ が書かれており、それ以外の $HW−N$ 枚のカードには何も書かれていません。
これらのカードに対し、以下の $2$ 種類の操作を可能な限り繰り返します。
・数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める
操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

・$1 \le H,W \le 10^9$
・$1 \le N \le {\rm min}(10^5,HW)$
・$1 \le A_i \le H$
・$1 \le B_i \le W$
・$(A_i,B_i)$ は相異なる
・入力に含まれる値は全て整数である

回答

回答1 (AC)

$HW$ 枚の全てのカードについて何が書かれているかを管理すると、$HW \le 10^9$ よりTLEになってしまいます。また $H$ や $W$ だけでも $10^9$ に近い値となる可能性があるため、$H$ や $W$ に関するループも TLE になってしまいます。このため、数字を書き込むカード情報の個数 $N$ に関するループだけで処理する必要があります。

設問では、数字が書かれたカードのない行と列を削除していきますが、行と列は独立しているので、ばらばらに処理することが可能です。まず行だけで考えましょう。数字の書かれたカードが存在する行の並びをソートすると、何行目を削除すれば良いかがわかります。数字の書かれたカードが存在する行に対しその行が何行ずれるか(その行までに何行が削除されたか)を記録していけば良いでしょう。列も同様です。コードは以下のようになりました。

abc213c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t h, w, n;
  cin >> h>> w >> n;

  vector<int64_t> a(n), b(n), c, d;
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i) >> b.at(i);
  }
  copy( a.begin(), a.end(), back_inserter(c) );
  sort( c.begin(), c.end() );
  copy( b.begin(), b.end(), back_inserter(d) );
  sort( d.begin(), d.end() );

  map<int64_t,int64_t> da;
  int64_t acounter = 1;
  for ( auto i=c.begin(); i!=c.end(); i++ ) {
    if ( *i==0 ) {
      da[0] = 0;
      acounter += 1;
    } else {
      if ( da.count(*i)!=1 ) {
        da[*i] = *i-acounter;
        acounter += 1;
      }
    }
  }

  map<int64_t,int64_t> db;
  int64_t bcounter = 1;
  for ( auto i=d.begin(); i!=d.end(); i++ ) {
    if ( *i==0 ) {
      db[0] = 0;
      bcounter += 1;
    } else {
      if ( db.count(*i)!=1 ) {
        db[*i] = *i-bcounter;
        bcounter += 1;
      }
    }
  }

  for ( int i=0; i<n; i++ ) {
    cout << a.at(i)-da[a.at(i)] << " " << b.at(i)-db[b.at(i)] << endl;
  }
}

AtCoder の解説 → ユーザ解説

「座標圧縮」というテーマの問題とのことでした。

AtCoder の解説 → ユーザ解説

lower_bound という関数を使うと、上記のコードがもっと精錬されるようでした。が、理解が追いついていません...