キーエンス プログラミング コンテスト 2019 D Double Landscape
所見
方針は外していなかった気がするけど微妙に間違っていた、こういうのがこれ(下)なんだと思う、くやC
ところで私はmdをプラグイン入れたVSCodeで書いてるんですが(プレビューを横で見たいので)、はてなブログに貼り付けた時に勝手にURL展開されてほしくないですか？
最近水色の人を見てると、青と水色の一番の違いは本当にここが大きいように見えていて、ここって正直競プロよりそれ以外の開発手法で学べるところな気もするので、いろいろ学んでほしい気持ちがある。https://t.co/TdxGxFeGR7
— chokudai(高橋 直大)🍆🍡 (@chokudai) December 18, 2018
問題概要
長さN,Mの列A,Bが与えられる。 N行M列のグリッドに1からN*Mまでの整数を重複なく書き込むとき、
- i行目に書き込まれている値のうち，最大の値はAi
- j行目に書き込まれている値のうち，最大の値はBi
となるような書き込み方はいくつあるか。1000000007で割ったあまりを求めよ。
取った方針
要するにi行目には必ずAiが含まれることを忘れており死亡
D、方針は行と列の最大値が同じところが固定されるので、それ以外の場所に大きい順に数を入れていく、数が置ける場所の個数は累積和っぽく持つことができる、という感じだったんですが
— AIRをプレイする (@ymduu) January 13, 2019
多分文章の意図が読み取れていないんですが、A[i]=B[j]の時はi行j列にその値が入るので先に決めてしまっていて(後出しで申し訳ないです)、あるマス目(i, j)はmin(A[i], B[j])より小さい数が入る、として入りうるマス目の個数を数えているので、A_iより大きい値がi行目のマスに入ることはないはずです？
— AIRをプレイする (@ymduu) January 13, 2019
これの何が嘘なのかようやくわかったんですが、これだとi行目にA[i]がある、j列目にB[j]があることが保証されない、かみぺさんのリプの大きいを小さいに変えると多分それがバグってるケースhttps://t.co/rXCIazdlIK
— AIRをプレイする (@ymduu) January 13, 2019
正しい方針
制約の厳しい大きい数から埋めていく。(貪欲をするときは制約が厳しい順に埋めていくテク)
i行目にはAiが、j列目にはBjが必ず含まれることに気を付ける。
- Ai == x && Bj == xのときxはi行j列に配置される
- Ai == x 、Bにxは含まれないときxはi行目のうちBj > x なる場所に配置される。Bにのみxが含まれる場合も同様(等号が含まれないのはAi != Bjで考えているため)
- AにもBにもxが含まれないとき、 Ai > x && Bj > xなる場所に配置される。このようなi, jの個数はxが置ける行 or 列を累積和っぽく持つことで高速に求めることができる(事前計算O(NM)、クエリO(1))
ここで、大きい数から埋めていったとき、Aにしか含まれない数A[k] == yを配置しようとした時にはA行目がすべて埋まってしまっており配置できないのでは、という疑問が発生する。
しかし、これは以下を考えることでありえないとわかる。
理由: 大きい数から埋めていくので、A[k] == yなる数を配置するときはその数がk行目に最初に入る数である。
考えてみると自明なんだけど、ちょっと迷うと時間が消えるのでキャッシュしておきたい
得られた知見
- 問題を誤読しない
- 貪欲をするときには制約が厳しい順に埋めていくテク
- 数列Aが与えられたとき、その要素よりも小さい(大きい)数は数列内にいくつあるか、というのは累積和に似た考え方で高速に求められる。
解くのに必要な要素
- 貪欲をするときには制約が厳しい順に埋めていくテク
- 累積和
- 場合の数
- i行目には必ずAiが含まれることを忘れない注意力
