Z法
AtCoder
AtCoder600点
ABC-F
文字列問題
ローリングハッシュ
KMP法
XOR
循環するものを二週させる
いもす法的変換
変数変換して扱いやすい同型な問題を見出す
数列
文字列検索問題
Z法
黄色diff
階差数列
バチャやった。13 位相当で割とよかった。 ロリハした。 問題へのリンク 問題概要 長さ の整数列 , が与えられる。以下の条件を満たす 以上 以下の整数 と、整数 の組をすべて求めよ。 = が成立する 制約 考えたこと 整数列 を circular shift した上で、 と…
AtCoder
AtCoder500点
ABC-E
DP
二次元ナップサックDP
文字列問題
SuffixArray
Z法
ローリングハッシュ
二分探索
文字列検索問題
全探索と二分探索の入れ替え
水色diff
連続部分列を扱う問題
もう文字列は怖くないっ!!! 文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける!!! Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editor…
ロリハの練習!!! 問題へのリンク 問題概要 長さ の文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ: S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の 文字が と一致す…
文字列問題
SuffixArray
KMP法
Z法
ローリングハッシュ
周期性に着目する
最適解の数え上げ
調和級数
互いに素
整数問題
文字列の周期
ARC-F
AtCoder
AtCoder900点
prefixとsuffix
文字列のconcatを考える問題
赤色diff
今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…