2019-09-16から1日間の記事一覧

同じ問題をZ-Algorithm, Suffix Array, Rolling Hashで解く

Quiz https://atcoder.jp/contests/abc141/tasks/abc141_e 3パターンで解いた。とはいえ完全に「けんちょん」さんの記事に依存している 解いた順に書く あとから検索する用に書いている。1度使ったコードは安心感があるため 1. ローリングハッシュ(ロリハ)…

ローリングハッシュの衝突回避と定数倍高速化

Quiz E - Who Says a Pun? https://atcoder.jp/contests/abc141/tasks/abc141_e Submission https://atcoder.jp/contests/abc141/submissions/7553482 衝突した状況 途中のデータでWA. 1つのロリハでは衝突してしまったのだろう 衝突回避のために取れる手段…

BITを2つ使って範囲更新・範囲和 (区間更新・区間和)

使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加える 範囲和 [a, b)の和を求める (計算量 : それぞれlog(N)) …