シコウノストレージ

自分自身の考えを整理するために書いています。

今日のキョウプロ

217のD

長さLメートルの直線状の木材があり、Q個のクエリが与えられるのでクエリに応じて地点Xを切るか、地点Xが含まれている木材の長さを出力せよという問題。

 

昨日考えていた解法。

まず、クエリが最大2*10^5個与えられるので残りは10^3くらいしか計算することができない。

L制約が大きいため配列を用意して切った場所を記録していくのは無理。

次にグループに分けるということでUnionFindを考えたがこれも制約により却下。

(実際は圧縮してやる方法もあるらしいのでこの後記述。)

最後にXの位置を記録しておき、その位置を二分探索して求められれば,right-leftで答えが求まるだろうと考えた。

二分探索自体の計算量はO(logN)なので、最大でも2*10^5なのでO(LlogL)になり間に合う。

しかし、これには一つ問題点があってソートがO(NlogN)なためそれでは間に合わない。

setを使ってみたりいろいろ考えたが結局この部分の計算量が減らせずに解けず。

 

答え

set+lower_bound,upper_boundでいける。

setで実装も考えたがsetだと二分探索で求めたインデックスにアクセスできないようなので断念していたがX以上の最小値を求めるloewr_bound,X以下の最大値を求めるupper_boundを使えば同じことが可能。

 

せっかくなので、lower_bound,upper_boundの中身についてみていく。

まず、set.lower_bound(x)の仕組みについて考えていく。

そもそも、setがインデックス指定でアクセスできないのでどうやっているのか。

まずは、setの仕組みについて知っておく必要がある。

https://cpprefjp.github.io/reference/set/set.html

setは連想コンテナの一種で、要素自身がキーになると書かれている。

要するにインデックスでアクセスはできず、要素でアクセスするということ。

これはfind(x)で行える。

このインデックスでアクセスできないというのは、コンテナの種類によってできるものとできないものがある。

Forward Iterator, Bidirectional Iterator, RandomAcccess Iteratorの3種類あり、それぞれ++itだけできる、++it,--itだけできる、++it, --it, it+=3ができるようになっている。

setはBidirectional IteratorでありBegin()+3みたいなことができないためインデックスにアクセスできない。

これがVectorであればできる。

詳しくは下記にて

https://rinatz.github.io/cpp-book/ch03-08-iterators/

 

上記で示したようにランダムアクセスで、二分探索で求めたLとRの差をsetで求めることはできない。

lower_boundの実装には二種類のやり方があって、lower_bound(set.begin(),set.end(),x)とset.lower_bound(x)では計算量がO(N)とO(logN)で大きく変わってくる。

 

前者はxの場所を求めるのに前と後ろからひとつづつずらしていくので線形時間がかかってしまう。

実装としては以下と同じ

f:id:slwmtin:20210905173911p:plain

これでも答えは求まるが、O(N)かかってしまうので今回のD問題だと,最大O(Q^2)の計算が必要になりTLE。

 

後者のやり方は、二分探索してやるのだが実装方法理解中()

後者のやり方を使うとO(QlogQ)になり、D問題がTLEにならずに通すことができる。

C++はset::upper_bound,set::lower_boundを使うことができるので簡単に実装可能。

 

f:id:slwmtin:20210905221123p:plain

 

217E

問題

クエリが個与えられ、列Aに対して以下の操作いずれかを行う。

1:Aの最後尾にxを追加

2:Aの先頭を出力

3:Aを昇順にソート

 

これも、本番中Priority_queueとqueueをうまく使って管理するのだろうという推察は行えたが、計算量の見積もりを誤ってしてしまっていた。

クエリが1ならqueueにpush、2の場合pryority_queueが空でなければ先頭を取得、削除空であればqueueの先頭を取得、削除する,3の場合はqueueに入れられている数をpriority_queueに入れる。

この際に,1.2はO(1)なので大丈夫だが、3でpriority_queueに移す際O(Q)かかってしまうのでないかと考えてしまい実装できなかった。

 

よくよく考えてみると、3を最後に1回だけ行う場合O(Q)かかってしまうが、それ以外は1,2だけということが保証できるのでO(Q^2)にはならない。

逆に頻繁に行う場合、1回ごとにpushする数は少なくQ回目の操作で3を行うなら全体でQ回しかプッシュを行わない。

つまり、どんなクエリが来ても全体でQ回より多くのpushは行われないということが言える。

解説によると、これの計算量を求め方を償却解析と呼ぶらしい。