Keyence2019 D. Double Landscape

atcoder.jp

考察

• D - 25個の整数で学んだように、最大値から順番に位置を決定していくのが筋がよさそう。
• 最大値から順に決めていくと、数字の位置を決めることで縦と横のそれぞれ最大値になるかならないかやその数が既に置かれたマスのx,y座標の集合を管理するだけでわかる。
• あとはその情報を用いてうまく数え上げられる。

感想

• つい最近解いた問題で得た教訓が生きてよかった。

Submission

void solve() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(M);
  cin >> A;
  cin >> B;
  vector<int> r(N * M, -1);
  vector<int> c(N * M, -1);
  for (int i = 0; i < N; i++) {
    A[i]--;
    if (r[A[i]] != -1) {
      cout << 0 << endl;
      return;
    }
    r[A[i]] = i;
  }
  for (int i = 0; i < M; i++) {
    B[i]--;
    if (c[B[i]] != -1) {
      cout << 0 << endl;
      return;
    }
    c[B[i]] = i;
  }
  mint ans(1);
  set<int> R, C;
  int num = 0;
  for (int i = N * M - 1; i >= 0; i--) {
    if (r[i] == -1 && c[i] == -1) {
      int pos = (int)R.size() * C.size() - num;
      if (pos <= 0) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(pos);
    } else if (r[i] == -1) {
      if (C.find(c[i]) != C.end()) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(R.size());
      C.insert(c[i]);
    } else if (c[i] == -1) {
      if (R.find(r[i]) != R.end()) {
        cout << 0 << endl;
        return;
      }
      ans *= mint(C.size());
      R.insert(r[i]);
    } else {
      if (C.find(c[i]) != C.end() || R.find(r[i]) != R.end()) {
        cout << 0 << endl;
        return;
      }
      R.insert(r[i]);
      C.insert(c[i]);
    }
    num++;
  }
  cout << ans << endl;
  return;
}