ABC023 C - 収集王
解法
まずは行目を選択すると固定して考えてみることにします。
行目を選択した場合にアメが個得られるとします。
同様に、列目を選択した場合に個得られるとします。
この時、個のアメを得るには、を満たすものならばいいように見えるかもしれませんが、実は違います。
にアメが存在していた場合、およびそれぞれにそのアメがカウントされているため、実際は個である可能性があるからです。
同様に、にアメが存在していた場合で、実際にを選択して個得られるパターンというのは、を計算するととなります。
しかし、にアメが存在していない場合は、となるマスが、求めるマスになります。
の種類はなので、全てを探索するわけにはいきませんが、となるようなマスの個数を求めるのは、二分探索を活用することで求めることができます。よって、うまいこと工夫をして、最初に述べた2種類のコーナーケースを考慮しつつ、計算ができるようにしたいです。
そこで、以下のようにすればよいことになります。
となるようなマスの個数を求める
を固定したとき、となるようなの個数がわかればよいです。これは、を昇順にソートすることで、二分探索を利用すればのとなっているの個数を求めることができます(upper_boundとlower_boundを求め、前者から後者をひけばよいです)。これを全てのについて行えばで計算できます。個のアメの座標について、となっているものが存在するかどうかを調べる
存在していたら、上の計算から引いてあげる必要があります。個のアメの座標について、となっているものが存在するかどうかを調べる
存在していたら、上の計算に足してあげる必要があります。
以上の計算をすることで、重複なく、求めたいマスの個数を数え上げることができます。
感想
最初、について二分探索をしたときに、辻褄が合わないマスが出てくることはすぐにわかったのですが、そこをどうするかで悩みました。
このような都合の悪いケースが出てきたときに、他の解法を探すか、そのケースだけうまく辻褄を合わせる方法があるかを調べる2択が発生すると思うのですが、今回ははずれを引きました。
ここら辺の勘というか経験といいますか、どちらについて考えればいいかがわかれば、ぐっと考察時間が短くなるような気はするのですが…