問題
ある旅館では、1 号室から N 号室まで N 個の部屋があります。
i 号室はAi 人部屋となっています。
この旅館ではD日間の工事が行われる予定で、d日目はLd号室からRd号室までを使うことができません。
d=1,2,…,Dのそれぞれの工事日について、稼働できる部屋のうち最も大きい部屋が何人部屋かを求めて下さい。
[制約]
🔹3≦N≦100000
🔹1≦D≦100000
🔹1≦Ai≦100
🔹2≦Ld≦Rd≦N−1
解き方・ソースコード
まずは、for文を使って泊まれる人数の最大値を計算する方法が思い浮かびますが、計算量がO(ND) となり実行するのに時間がかかってしまいます。
計算量を減らすために、L 号室から R 号室まで以外の部屋が使えるとき「最も大きい部屋は何人部屋か」を次の式で計算します。
max(1~(L−1)号室の最大人数,(R+1)~N号室の最大人数)
1号室からi号室までの最大人数Pi、およびi号室からN号室までの最大人数Qiを求めると、d日目の答えはmax(QLd−1,QRd+1)で計算することができます。
次に、Pi,Qiを求めるために、累積和と同じような方法を使うことができます。
Piについては先頭要素Aiから累積的に最大値を計算し、Qiについては最終要素ANから累積的に最大値を計算しておくと、計算量O(N)でそれぞれの値を求められます。
[Google Colaboratory]
1 | #--------- 入力例 1 --------- |
[実行結果(入力例1)]
工事1日目に使える最も大きい部屋数は3人部屋 工事2日目に使える最も大きい部屋数は5人部屋
工事日ごとに使える部屋のうち、最も大きい部屋が何人部屋かを求めることができました。