ABC158 F を解いた 。lower_bound と SegmentTree を使っている。

ロボットを x でソートしておく。

組み合わせの数を dp で解く。あるロボットを操作したときと操作しなかったときの組み合わせの数を足せばよい。操作したときは連鎖的に操作されるロボットの右のロボットまでの組み合わせの数。操作しなかったときは右のロボットまでの組み合わせの数。右から順に確定して答えは dp[0] に入る。

連鎖的に操作されるロボットのうち最も右のものの添字。単純な方法は [x, x + d) の x をもつロボットのうち最大のものを探索する。右から順に走査する。これが直接操作するロボットから起動されるもの。連鎖的に……を求めるためにこの探索を再帰的に呼び出して最大のものを取る。この単純な方法だと n が大きいと間に合わない。直接操作の部分は x でソートしてあるため lower_bound で短縮できる。連鎖的に……は SegmentTree で短縮できる。得られた添字からロボットの添字の区間 l..r が得られる。この各区間における最大の添字を SegmentTree によって管理する。右から順に探索・更新を繰り返せば目的のクエリのための SegmentTree ができる。

SegmentTree のところが思いつかなかった。

子どもの看病のために仕事を休む。なにやら発疹ができているような……。子どもをほとんど一日抱っこさせられていてぼくがひどく疲れている。

いろいろ届いた (2020-03-09) 。設定など何もできていない。

寝かしつけでそのまま寝てしまった。 23:00 のカウントはリセット。