7K12 blog

猫でも分かるアルゴリズム解説

ABC138 E - Strings of Impurity

f:id:tkr987:20200513221305p:plain

https://atcoder.jp/contests/abc138/submissions/13182121

  • index[l, r]の要素数は半開区間[l, r+1)で考えると(r+1)-lで計算できる

f:id:tkr987:20200513224046p:plain

例えば、T[2]=rをSから検索する方法を考える。これを検索するにはT[1]=hの情報が大事になる。T[1]=S[4]=hだとすると

  1. S[4]以降のSにrがある→S[4]以降で最初に見つかったrを採用する
  2. S[4]以降のSにrがない→Sの終端まで行ったあと先頭に戻って最初に見つかったrを採用

の2つに場合分けされる。rがS[4]以降に存在するかどうか(h-index=4以降にrが存在するかどうか)を高速に調べるには二分探索をする。前処理でSの要素のうちaである全てのindexをメモしておき、同様にzまでindexをメモしておく。前処理によりSの要素全てのindexをメモした配列a-memoからz-memoが出来上がるが、このメモ配列に対してupper_bound(all(r-memo), h-index)、つまりメモの二分探索、をすれば実現できる。あとは ans[i] = ans[i-1] + 緑矢印の長さ を計算していくと最小値が求まる。