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つ使って範囲加算・範囲和 (区間加算・区間和) range add

注意 range add, range updateは区別しよう 今回はrange add 使った問題 C - Attack Survival https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加…