Double Landscape -AtCoder KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019 D-

500点です。
問題リンクを貼っておきます。
D - Double Landscape

簡潔な解説は公式のものがわかりやすいので、ここには冗長な思考過程を書いていこうと思います。

考察の流れ

テストケースがややこしいやつと貧弱なやつしかないので、手元で手頃なやつを生成します。

とりあえず手元で考えてみようということで、こんな図を描きました。
丸で囲まれた数字は、そのマスにこの数字が入ることが確定していることを表します。
細長い丸とその脇に書かれた小さい数字は、この数字の入るマスの候補はこの範囲だということを示しています。

もしかして、この細長い丸はお互いに重複することがないのではないか？と考えます。
ここで落ち着いて、細長い丸を描くときのルールを考えてみます。
上側に並んでいる数字をa[i]、左側に並んでいる数字をb[j]とすると、
(i, j)のマスは
a[i] < b[j]の場合は縦に細長い丸に、
a[i] > b[j]の場合は横の細長い丸に入る可能性があるようです。

すると、a[i] < b[j]とa[i] > b[j]は同時に成立しないので、一つのマスは縦横の丸に重複して含まれることがありません。これでだいぶ考えるのが楽になりました。重複していると、その重複しているマスに数字が入る場合/入らない場合についてそれぞれ考えなければいけないので、ややこしくなってしまう気がします。
また、わかりやすいように上と横に並んでいる数字をソートしても答えは変わらないようです。

細長い丸は見にくいので細長い棒になりました。
わかりやすくなってきました。

ややこしかった入出力例4もExcelに突っ込んで図を描いてもらいましょう。
ちょっとだけ線の引き方のルールが変わっちゃてますが気にしないでください。先ほどは位置が確定した行/列には空白のマスがありましたが今回は気にしていません。

こうなると線の引かれ方のルールもかなりわかりやすいですね。
先ほど式で表したルールを考えるとこのようになるのは当然なのですが、僕は図にしないとやっぱりピンとこないなと思いました。

この図を見ながら考えます。
グリッドを1からN*Mの数字で重複がないように埋めていくわけですが、この数字は3つのグループに分けることができます。

1. 縦横どちらにも数字が載っているので、入るマスが決まるもの
2. 縦横のどちらかに数字が載っているので、入る行/列が決まるもの
3. 縦横のどちらにも数字が載っていないので、各行/列の最大値を超えない範囲でどこにも入れるもの

です。

大きい数字は入るマスが決まりやすそうなので、大きい数字から順番に考えていきます。
答えを格納する変数ansを1で初期化して用意しておきます。

182や179などはグループ1に属します。これらは位置が確定しているので、ansの値は変わりません。

177はグループ2です。入る行が確定しています。

この写真で青く囲った部分です。この場合はansに5をかけます。

174はこの図にはいません。グループ3です。ということは、各行/列の最大値を超えない範囲ではどこにでも入れます。

この青く囲った範囲に入ることができます。
この場合はansにを掛ければいいと思いそうになりますが、そうではありません。
この範囲にはすでに175から182が入っているからです。
これらの数字を入れた上で174が入れるマスはいくつあるか、ということを考えなければならないので、ansにはを掛けます。

これで、各数字についてどういう操作をすれば答えが求まるかを考えることができました。

実装について

簡単に述べます。僕の実装はです。解説にはとあったので改善できるのだと思いますが僕にはわかりませんでしたorz

• ある数字が上/左に存在しているかどうかを素早く確認できる
• ある数字以上の数字のうち、最小のものが何番目かを素早く確認できる

という特性を備えたデータ構造が望ましいような気がします。
僕はstd::set<pair<int, int> >を使いました。firstには並んでいる数字の値、secondにはその数字が何番目のものなのかを保管しておきます。
その上でlower_boundを使うと上記の操作が行えます。

僕のレベルではこれが精一杯でした
僕は#define int longをしているので、このコードをそのまま貼り付けるとintのせいで通らないことがありえます。

▶ソースコードを開く

const int MOD = 1000000007;

typedef std::pair<int, int> P;

int n, m;
int a[1000];
int b[1000];
int ans = 1;
std::set<P> ast, bst;

signed main(){
	scanf("%ld %ld", &n, &m);
	for(int i = 0; i < n; i++){
		scanf("%ld", &a[i]);
	}
	for(int i = 0; i < m; i++){
		scanf("%ld", &b[i]);
	}
	
	std::sort(a, a+n, std::greater<int>());
	std::sort(b, b+m, std::greater<int>());
	
	for(int i = 0; i < n; i++){
		ast.insert(P(a[i], i));
	}
	for(int i = 0; i < m; i++){
		bst.insert(P(b[i], i));
	}
	
	for(int i = n*m; i > 0; i--){
		auto ita = ast.lower_bound(P(i, 0));
		auto itb = bst.lower_bound(P(i, 0));
		int product;
		if(ita == ast.end() || itb == bst.end()){
			product = 0;
		}else if(i == ita -> first && i == itb -> first){
			product = 1;
		}else if(ita -> first == i){
			if(itb == bst.end()){
				product = 0;
			}else{
				product = itb -> second + 1;
			}
		}else if(itb -> first == i){
			if(ita == ast.end()){
				product = 0;
			}else{
				product = ita -> second + 1;
			}
		}else{
			product = (ita -> second + 1) * (itb -> second + 1) - (n*m - i);
		}
		ans *= (product % MOD);
		ans %= MOD;
	}
	printf("%ld\n", ans);
	return 0;
}

lower_boundがend()を返す場合についての処理が抜けていて、1WAを生んでしまいました。setを扱うのは僕には難しいです。慣れたいですね。

誤りの指摘や質問等あれば僕のTwitterやコメントまでよろしくお願いします。