trie木
AOJ
JAG
AOJ-ICPC500点
文字列問題
制約:複数系列の長さの合計が10^5以下
総和がNになる整数組の種類数はO(√N)
DP
区間分割型ナップサックDP
DP高速化:遷移先が限られる
平方分割
文字列検索問題
ローリングハッシュ
Aho-Corasick法
trie木
数え上げ問題
区間
連続部分列を扱う問題
AOJ-ICPC
JAG模擬地区
変化・遷移が限られる
めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…
Codeforces
禁止文字列
文字列問題
DP
ナップサックDP
状態遷移を意識するDP
ワイルドカード問題
trie木
最大スコア
連続部分列を扱う問題
CodeforcesDIV2
CodeforcesR2200
部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…
Codeforces
グラフ問題
木
木上の最大マッチング問題
マッチング
Greedy
Greedyなマッチング
葉から考える
trie木
カッコ列
ナップサックDP
DP
CodeforcesDIV2
CodeforcesR2000
こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…
いい感じの Greedy 問題 問題へのリンク 問題概要 個の文字列 が与えられる。2 つの文字列 について、 の最後 i 文字と、 の最後 i 文字が共通 の後ろから i 文字目も、 の後ろから i 文字目も c である という条件を満たすとき、ラベル (i, c) をつけながら…