AtCoder ABC 150 F - Xor Shift (黄色, 600 点)

AtCoder AtCoder600点 ABC-F 文字列問題ローリングハッシュ KMP法 XOR 循環するものを二週させるいもす法的変換変数変換して扱いやすい同型な問題を見出す数列文字列検索問題 Z法黄色diff 階差数列

バチャやった。13 位相当で割とよかった。ロリハした。問題へのリンク問題概要長さの整数列 , が与えられる。以下の条件を満たす以上以下の整数と、整数の組をすべて求めよ。 = が成立する制約考えたこと整数列を circular shift した上で、と…

2019-09-16

AtCoder ABC 141 E - Who Says a Pun? (水色, 500 点)

AtCoder AtCoder500点 ABC-E DP 二次元ナップサックDP 文字列問題 SuffixArray Z法ローリングハッシュ二分探索文字列検索問題全探索と二分探索の入れ替え水色diff 連続部分列を扱う問題 lcp

文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける！！！ Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索「ロリハ + 二分探索」の高速化 (editorial のラスト 3 行で言及された…

2019-03-12

AOJ 2934 往復文字列 (RUPC 2019 day3-E)

AOJ RUPC 文字列問題文字列検索問題回文 Manacher法 Z法ローリングハッシュ調和級数

ロリハの練習！！！問題へのリンク問題概要長さの文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ: S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の文字がと一致す…