ABC248で得た学び
今日はA,Bだけ解けて、Cは考えたけど難しそうすぎて飛ばしました。
その後のD問題を後から友達と答え合わせする中で得られた学びを記します。
-
- ソート済み配列に対するBisectを使ったインデックス取得
D問題では、ソート済みの配列からある数L,Rについて、"L<X<R"を満たすような要素の数を取得する必要がありました。
僕は初め数列内のすべての要素に対してL<X<Rを比較して、それを満たしている要素の数をカウントしていたのですが、それではTLEとなりました。
これにたいして必要だったのが、配列の要素の中の、Lが入る位置、Rが入る位置を取得するという処理です。配列はソート済みなので、Lが入る位置からRが入る位置までの間の要素数が、最終的に求めたい"L<X<R"を満たすような要素の数となります。
Pythonではbisectというライブラリを使うことでソートされた配列の中に新しい要素を入れる際の位置を簡単にかつ高速に取得できるため、思いつきさえすれば実装も可能だったと思います。
- ソート済み配列に対するBisectを使ったインデックス取得
-
2 辞書型の要素があるかないかの判定
辞書型の要素に対して、「あるキーKに対応する値が存在すればAという処理を、なければBという処理を行う」という場合があり、自分は今までTry-exceptを使った処理を実施していました。しかし、これは実際に競技プログラミングでは非常に重い処理らしいです。
このような処理を行いたい時に有効なのが、dict.get("key")という関数。これは、対応する値があればそれを返し、なければNoneを返すものらしいです。そのため、この関数の返り値に応じて条件分岐をすることで、キーが存在するかしないかの処理を分けることができます。