ARC067F YakinikuRestaurants
はじめに
解いて印象に残った問題の概略はツイッターに書き込んでいたのですが、それだとネタバレになってよくないので、ブログに書くことにしました。(あくまでも自分の理解のために書いているだけなのでそこまで真剣には書いていません。ご了承くださいm(__)m)
「YakinikuRestaurants」は初めて問題を見てから二か月以上、時々考えていたのですがやっと解くことができました。
解説と全然違う解き方だったので、記事にすることにしました。
問題
1<=i <=j<=Mに対し、
happy(i,j):入った焼き肉店のうち左端が店i,右端が店jであるときの幸福度の最大値
とおきます。
min{happy(i,j):1<=i<=j<=N}を求めればよいです。
各happy(i,j)の計算は安直な方法だとO(M)とかO(MlogN)かかるので、TLEしてしまいます。なんらかの工夫が必要です。
そこで、次の2つの方針を考えました。
1．happy(i,j)を高速に計算する。
2．F(i)=min{happy(i,j):i<=j<=M}を高速に計算する。(O(M)とかO(N)ならOK。O(NM)はアウト)
1は厳しそうだったので、2を中心に考察します。
F(i)=f(i,j)となるようなjをG(i)とおきます(i<=G(i)<=N)。G(i)としては複数の値が考えられますが、一番小さいものでもとっておけばよいです。
このG(i)の値に注目しながら、頭の中でぐだぐだと考えていると、Gがiに関して単調増加であることに気づきました。
(証明はちゃんと書くと大変だけど、正しいはず。)
単調増加といえば尺取り法なので、G(1)からG(N)の値を尺取り法の要領で計算すればよさそうです。
でも、実はうまくいきません。尺取り法でG(i)の値を計算するためには、happy(i,j)(max(i,G(i-1))<=j<=N)の値をすべてみないといけないからです。
ここで困り果ててしまったのですが、どきんさんは日ごろの行いが良いので、天啓が降ってきました。
G(i)の値を計算する順番を工夫することで、計算量を大幅に削減できるのです。
たとえば、G(1)をはじめ計算するのではなくG(N/2)を計算してみましょう。
するとこれ以降の計算では、
・G(i)(i < N/2)については、happy(i,j)(i<=j<=G(N/2))
・G(i)(i>N/2)については、happy(i,j)(max(i,G(N/2))<=j<=N)
をみれば十分なので、G(N/2)の値によらず、探索空間が一気に半分になります。
以下同様に、中間を縫うように計算していけば、happy(i,j)の計算回数は高々O(NlogN)回にできます。
各happy(i,j)はセグ木を使えばO(MlogN)で計算できるので、全体の計算量はO(NM(logN)^2)となり、まにあいます。
実装
セグ木をM本用意しないと解けないのですが、やり方がわからず困り果てていました。
ABC157Eにセグ木を26本使って解く方法があることを思い出し、他の方の提出を見ると、Segment_Tree < vector< int>> としてあって、「あーたしかにー」ってかんじでした。。
重い実装でしたが、想定よりも少ないバグで解くことができました(set
でもコンテスト中に解くのはきびしそうです。がんばりたいです。
公式解説では、happy(i,j)を高速に求める方針を用いていました。しっかり図を描いて検証すれば、公式解説の方針に用意気づけたのではないかと思うと残念です。
私と同じ解法の方は見つけられなかったのですが、ここで用いたテクニック(?)に名前がついているのを知っている方がいれば、教えていただけるとうれしいです。
追記:上記のhappyのようにmin{happy(i,j):i<=j<=M}なるjが単調増加であるような関数のことをmonotone minimaとよび、上のように最小値を求める方法は一般的なテクのようです。教えていただいた方、ありがとうございました。
