ABC077 C - Snuke Festival

1年以上振りの投稿

問題

長さNの自然数の配列A, B, Cが与えられる。
a∈A, b∈B, c∈Cとする。
a<b<cとなる組み合わせの個数を求めよ。

AtCoderの解説

配列AとCをソートして、配列Bの各値bについて、bより真に小さい配列Aの要素数とbより真に大きい配列Cの要素数を二分探索を用いて求める。ただし、配列AとCには同じ数字が複数ある可能性があるため、探し方には注意する。

Python3だとbisect.bisect_leftとbisect.bisect_rightを用いるとよい。

時間計算量O(N*logN)

二つのやり方で解いた。

配列A, B, Cをソートする。配列Bの最も大きい要素より大きいCを後ろから順番に探す。その次に大きいBの要素をCから探すが、前に探したとこより前（後ろ）にあるため、それを利用する。この手法によりBの値を固定した時のCの値の個数がわかる。

配列Aを小さい方から見ていく。配列Aの一番小さい要素より初めに真に大きくなるBの要素を順番に探して見つける。Aの要素を固定したとき、 BとCの要素の組み合わせは先ほど求めた配列の累積和となっているためあらかじめ求めておく。

配列Aの次に小さい要素は先ほど見つけたBの要素よりは後ろにあるはずなので、探す。

これらの手法は全てO(N)で計算可能であるため、通る。

結構好きかもしれない。

(25分)

whoami