SparseTable
AtCoder
有志コン
文字列
文字列検索問題
Manacher法
回文
二分探索
天才な二分探索
区間
クエリ処理問題
クエリ:区間
前処理
セグメント木
RMQ
SparseTable
連続部分列を扱う問題
最大回数・最大個数を求める
そのまま覚えたいシンプル設定の中堅以上の典型問題
最適化問題
区間の長さの最大値または最小値を求める
ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…
コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに!」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…
AOJ
AtCoder
JAG
AOJ-ICPC
AOJ-ICPC700点
JAG夏合宿
二分探索
二分探索:lower_bound
文字列
セグメント木
SparseTable
SuffixArray
文字列検索問題
クエリ処理問題
制約:複数系列の長さの合計が10^5以下
連続部分列を扱う問題
区間
区間の長さの最大値または最小値を求める
解空間:O(N^2)個の区間
解空間:O(N^2)通りの選択肢
そのまま覚えたいシンプル設定の中堅以上の典型問題
Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…
Disjoint Sparse Table の勉強をした!!! 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…