KEYENCE Programming Contest 2019：D - Double Landscape

atcoder.jp

方針

はソートしてよいです。なぜなら、これは行や列を入れ替えることに対応しているからです。以下 はソートされているとします。

まず の中に同じ値が2つ以上ある場合、答えは 0 です。問題の条件より 行目には必ず があるので、2行以上に同じ値が存在することになってしまうからです。 についても同じことが言えます。以下 に同じ値はない、すなわち のとき とします。

問題の条件から、大きな値ほど入れられるグリッドの範囲が狭くなります。そこで、 から順番にグリッドに詰めていくことを考えます。(NMの入る場所)×(NM-1の入る場所)×…… を計算していけば答えが求まります。

(1) を満たす が存在するとき
を入れられる場所は i 行 j 列のみの 1 通りです。なお、ここが既に他の値で埋まっていることはありません。いま大きな値から順に詰めており、 より大きな値は i + 1 行以降、j + 1 列以降に詰まっているからです( はソートされています)。

(2) を満たす が存在するとき
が i 行目に入るのは確定で、そのうち となる行が候補となりますが、この候補の中に既に他の値が埋まったマスはありません。なぜなら、既に埋まった値は全て より大きな値なので、それが最大値が である i 行目に入るのは矛盾だからです。よって を満たす j の数が の入る場所の数となります。

(3) を満たす が存在するとき
(2)と全く同様です。 を満たす i の数を数えればよいです。

(4) を満たす が存在しないとき
( を満たす行の数) × ( を満たす列の数) のマスが を入れるマスの候補となりますが、これまで入れてきた全ての値はこれら候補の中に入っています。よって ( を満たす行の数) × ( を満たす列の数) - (NM - x) 通りとなります。この場合、 を入れられるマスが一つも残っていないこともあります。そのときは 0 を出力します。

はソートしてあるので、「 を満たす の存在確認」や、「 を満たす行の数」などは二分探索で行えます。よって計算量は となりました。

具体例

入力例 4 の場合です。
から始め、 までは上記の (1) の場合に当たるので、1か所ずつ埋めていきます。 のとき、(3) にあたり、図の通り 5 通りとなります。

このあと までは1か所ずつ埋まっていきます。 のときは (4) にあたり、図の通り 56 - 8 = 48 通りとなります。なお図の緑のマスのうち、どこか1か所に 177 が入っています。

以降も同様です。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N, M;  cin >> N >> M;
    vector<int> A(N), B(M);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<M; i++) cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(int i=1; i<N; i++) if(A[i]==A[i-1]){ puts("0");  return 0; }
    for(int i=1; i<M; i++) if(B[i]==B[i-1]){ puts("0");  return 0; }

    int mod = 1e9+7;
    ll ans = 1;
    for(int i = N*M; i>=1; i--){
        if(binary_search(A.begin(),A.end(),i) && binary_search(B.begin(),B.end(),i)) continue;
        else if(binary_search(A.begin(),A.end(),i)){
            ans = (ans*(B.end() - lower_bound(B.begin(),B.end(),i)))%mod;
        }else if(binary_search(B.begin(),B.end(),i)){
            ans = (ans*(A.end() - lower_bound(A.begin(),A.end(),i)))%mod;
        }else{
            int h = A.end() - lower_bound(A.begin(),A.end(),i);
            int w = B.end() - lower_bound(B.begin(),B.end(),i);
            ans = (ans * (h*w - (N*M - i)))%mod;
        }
        if(ans == 0) break;
    }

    cout << ans << endl;
}