ARC155に出た。

A: こんなのAに配置するのはバカなのか？

文字列$A$を反転したものをR(A)、文字列A,Bを結合したものをA+Bと表記することにする。

頑張って帰納的に考察すると、S’は文字列R(S)+S+R(S)+S+…の先頭K文字であり、またかつ文字列…+S+R(S)+S+R(S)の後尾K文字であることがわかる。この2つが一致するかどうかを判定すればよいが、Kは非常に大きいので周期性を利用する。

Kを2Nで割ったあまりをmとする。S+R(S)をmだけ回転させた文字列とR(S)+Sが一致していればOK。

B: 異常に簡単だった。これをAに置くべきだろ。

||x-a|-b|のグラフを描いてみると、a-bおよびa+bで最小値をとるW字型のグラフとなることがわかる。これはmin(|x-(a-b)|, |x-(a+b)|)に等しい。よって、集合Sの任意の(a,b)に対するa+bとa-bを集めた集合をPとすれば、f_S(x)の値はPの要素とxの差の最小値として求められる。

集合Pの大きさは高々2Q個で、これをstd::setで管理してやればクエリ2の結果は簡単に求めることができる。[a,b]の区間にPの要素が存在すれば0、存在しなければa以下最大の要素とaの差、b以上最小の要素とbの差のminをとる。

---

筋トレをした。2日空けてしまった。今日は腕立て。

---

Vulkanの記事の改訂作業を進めた。移行後の新サイトに反映する予定なのでしばらくはこの改訂内容が出ることはないが。

家で捗らないので、バーガー屋でおやつを食べつつ作業したらかなり進んだ。