けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

SparseTable

ウクーニャたんお誕生日コンテスト D - ukuku

ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…

AtCoder ABC 282 F - Union of Two Sets (青色, 600 点)

コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに!」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…

AOJ 2644 Longest Match (JAG 夏合宿 2014 day4-F) (700 点)

Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…

Codechef Product on the segment by modulo

Disjoint Sparse Table の勉強をした!!! 詳しいことは Disjoint Sparse Table と セグ木に関するポエム (のししゃん) Codechef Tutorial - Disjoint Sparse Table あたりを参考に。 問題概要 数列が与えられて、「区間 [L, R) の積を P で割ったあまりを…