2017-05-06から1日間の記事一覧

yukicoder #515: 典型LCP

事前に文字列を辞書順にソートしておく。l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。|lcp(l, r)| <= |lcp(l+1, r)|が成り立つからlcp(l, r)= lcp(lcp(l, l+1), lcp(l+1, r))よって、長さx以下のprefixについて、lcp(i, j)を求め…

宝探し3 | yukicoder

f(X, Y)を質問(X, Y)の結果とすると f(0, 0) + f(10^9, 0) = 10^9 + 2AY AY = (f(0, 0) + f(10^9, 0) - 10^9) / 2 求まったAYを利用して AX = f(0, AY)