ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC023 C - 収集王

問題
提出コード

解法

まずはi行目を選択すると固定して考えてみることにします。
i行目を選択した場合にアメがr_{i}個得られるとします。
同様に、j列目を選択した場合にc_{j}個得られるとします。
この時、K個のアメを得るには、r_{i} + c_{j} = Kを満たすものならばいいように見えるかもしれませんが、実は違います。
(i,j)にアメが存在していた場合、r_{i}およびc_{j}それぞれにそのアメがカウントされているため、実際はK-1個である可能性があるからです。
同様に、(i,j)にアメが存在していた場合で、実際に(i,j)を選択してK個得られるパターンというのは、r_{i} + c_{j}を計算するとK+1となります。
しかし、(i,j)にアメが存在していない場合は、r_{i} + c_{j} = Kとなるマスが、求めるマスになります。
(i,j)の種類はRCなので、全てを探索するわけにはいきませんが、r_{i} + c_{j} = Kとなるようなマスの個数を求めるのは、二分探索を活用することで求めることができます。よって、うまいこと工夫をして、最初に述べた2種類のコーナーケースを考慮しつつ、計算ができるようにしたいです。
そこで、以下のようにすればよいことになります。

  • r_{i} + c_{j} = Kとなるようなマスの個数を求める
    iを固定したとき、c_{j} = K - r_{i}となるようなjの個数がわかればよいです。これは、c_{j}を昇順にソートすることで、二分探索を利用すればK - r_{i}のとなっているc_{j}の個数を求めることができます(upper_boundとlower_boundを求め、前者から後者をひけばよいです)。これを全てのiについて行えばO(R log C)で計算できます。

  • N個のアメの座標(x,y)について、r_{x} + c_{y} = Kとなっているものが存在するかどうかを調べる
    存在していたら、上の計算から引いてあげる必要があります。

  • N個のアメの座標(x,y)について、r_{x} + c_{y} = K+1となっているものが存在するかどうかを調べる
    存在していたら、上の計算に足してあげる必要があります。

以上の計算をすることで、重複なく、求めたいマスの個数を数え上げることができます。

感想

最初、Rについて二分探索をしたときに、辻褄が合わないマスが出てくることはすぐにわかったのですが、そこをどうするかで悩みました。
このような都合の悪いケースが出てきたときに、他の解法を探すか、そのケースだけうまく辻褄を合わせる方法があるかを調べる2択が発生すると思うのですが、今回ははずれを引きました。
ここら辺の勘というか経験といいますか、どちらについて考えればいいかがわかれば、ぐっと考察時間が短くなるような気はするのですが…