2022-12-15から1日間の記事一覧
AtCoder
unrated公式コン
橙色diff
SuffixArray
場合分け
辞書順
Greedy
prefixとsuffix
文字列
操作
操作:挿入
操作:1文字を変更する
操作後の結果の最適化問題
操作の流れを単純化する
操作をちょうどK回行う
思わず解きたくなる興味深い良問
そのまま覚えたいシンプル設定の中堅以上の典型問題
Greedy:辞書順最小を求める
とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…
AtCoder
ACLpractice
文字列
SuffixArray
prefixとsuffix
数え上げ問題
ダブルカウントを防ぐ場合分け
最小添字規則によってダブルカウントを防ぐ
解空間:O(N^2)通りの選択肢
区間
連続部分列を扱う問題
種類数
lcp
そのまま覚えたいシンプル設定の中堅以上の典型問題
Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題! 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…