Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題！ 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…

Floor Sum が AtCoder 標準ライブラリに入ったのはびっくりした。結構マニアックな印象だった。 問題へのリンク 問題概要 この問題は ケース与えられる。整数 が与えられるので、 を求めよ。 制約 考えたこと 等差数列を で割った商の総和を求めたくなること…

BIT の使い方の練習問題。同時に、自分で BIT を書いたときにそれを verify できる問題でもある！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する 個のクエリに答えよ。 ：数列中の値 に を加算する (a[p] += x) ：数列 の区間 の総和…

Union-Find の最も典型的な練習問題 問題へのリンク 問題概要 頂点 辺の無向グラフに 個のクエリが飛んでくる ：辺 を追加する ： 頂点間 が連結ならば 1、そうでないなら 0 を出力する 制約 解法 Union-Find はグループ分けを管理するデータ構造です。以下…