KEYENCE Programming Contest 2019 D - Double Landscape (500)

D - Double Landscape

概要

項の数列と、項の数列が与えられる。
マスにからまでの数字を1つずつ入力することを考える。
各について、行目に入力された数字の最大値が、行目に入力された数字の最大値がであることを満たすような数字の入力方法は何通りあるか。
(mod して出力)

制約

方針

解答は数列、数列のそれぞれの順番によらないので、数列、数列をソートして考える。
行目がであるならば、行目のどこかの列にを入力しなければならないことに注意する。

数列、数列はそれぞれユニークでなければならない。
もしユニークでなければ、複数行・列に数値を書き込まなければならないので入力不可。

入力する数値はから大きい順に確認していく。
入力する数値をとすると、下記の場合でロジックを考えればよい。

• がどちらにもにあるとき
• がのみにあるとき
• がのみにあるとき
• がどちらにもないとき

「がどちらにもないとき」は、入力対象となるマスの数から、これまでに入力した数字の数を除いた分だけ組み合わせが存在する。
この計算の結果、入力可能なマスがないこともあり、その場合は全体の答えがになる。

感想

ほぼ解説どおり。
テストケース2をはじくようなコーディングが難しいと思ったが、
解説のやり方だと勝手にはじかれるので、うまいやり方だと思った。

解答

Submission #4039062 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
// v is sorted
bool isUnique(vector<ll> v){
	rep(i, v.size()-1){
		if(v[i] == v[i+1]) return false;
	}
 
	return true;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M;
	cin >> N >> M;
 
	vector<ll> A(N);
	rep(i, N) cin >> A[i];
	sort(A.begin(), A.end());
	if(!isUnique(A)){
		cout << 0 << endl;
		return 0;
	}
 
	vector<ll> B(M);
	rep(i, M) cin >> B[i];
	sort(B.begin(), B.end());
	if(!isUnique(B)){
		cout << 0 << endl;
		return 0;
	}
 
	ll MOD = 1e9 + 7;
	ll ans = 1;
 
	for(ll x = N * M; x >= 1; x--){
		int ia = lower_bound(A.begin(), A.end(), x) - A.begin();
		int ib = lower_bound(B.begin(), B.end(), x) - B.begin();
		if(ia >= N || ib >= M){
			cout << 0 << endl;
			return 0;
		}
 
		if(A[ia] == x && B[ib] == x) continue;
 
		if(A[ia] == x){
			ans *= M - ib;
			ans %= MOD;
			continue;
		}
 
		if(B[ib] == x){
			ans *= N - ia;
			ans %= MOD;
			continue;
		}
 
		ans *= max((N - ia) * (M - ib) - (N * M - x), 0LL);
		ans %= MOD;
	}
 
	cout << ans << endl;
}