KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019：D - Double Landscape
問題
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_d
考え方
一番大きい数から置いていくとして考えていく。これは後ろの数ほど制約が厳しいことから、後ろの数のほうが置きやすいことから分かる。またすべての場合の数を求めることからそれぞれソートすることができる。よって数列を降順でソートしておくこととする。
そうしたときにある数 が
にも
にも含まれる場合は置くマスは一意に決まることがわかる。
また、ある数 が
か
の一方しか存在しない場合について考えていく。
に含まれているとする。対称性から
も同様である。そのとき数
の置く行は一意に決まる。どの列に含めるかはその数以上の列のマスに置くことができる。置けるマスはどのマスにおいてもよい。
が
にも
にも存在しない場合は、
の
以上の長方形が置けるマスの候補になる。ただしすでに置いたマスには置くことができない。これはすでに置いたマスの数をカウントしておくことで求めることができる。
Submission #4014052 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019
どこに着目して考察するべきだったか
すべてのパターンの数え上げであるから、ソートすることができるのでソートする。また、数を大きい数から順番に決めていくことが最適である。大きい数ほど制約が厳しいためである。
何がバグっていたか
の
TLE 解の結果から大きい数から決めていく方針であっていることはわかったが、ソートしてよいことに気づくことができず、それぞれ置く際に置けるマスの候補を で求めることができなかった。
得た知見
- 制約が厳しい数から順に決めていく
- すべてのパターンを決めるときにソートすることができる
