最小添字規則によってダブルカウントを防ぐ
CSAcademy
文字列問題
SuffixArray
lcp
禁止文字列
与えられた文字列を連結した文字列を考える
そのまま覚えたい典型問題
O(N^2)個のものを考える問題
最小添字規則によってダブルカウントを防ぐ
ダブルカウントを防ぐ場合分けのテクニック
数え上げ問題
連続部分列を扱う問題
SuffixAutomation
文字列の連続した部分文字列を数え上げるのは Suffix Array の典型問題。それを少し応用した面白い問題! 問題へのリンク 問題概要 英小文字からなる 2 つの文字列 が与えられる。次の条件を満たす文字列の個数を求めよ。 中に連続した部分文字列として含ま…
AtCoder
ACLpractice
文字列問題
SuffixArray
累積和
prefixとsuffix
数え上げ問題
ダブルカウントを防ぐ場合分けのテクニック
最小添字規則によってダブルカウントを防ぐ
O(N^2)個のものを考える問題
区間
連続部分列を扱う問題
種類数
lcp
そのまま覚えたい典型問題
Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題! 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…
AtCoder
AtCoder600点
ABC-F
数え上げ問題
順列
順列を巡回群の直積と見る
最小添字規則によってダブルカウントを防ぐ
DP
区間分割型ナップサックDP
数珠
グラフ・盤面・数列の個数の数え上げ
二項係数
条件の言い換え
K以上からK+1以上を引く
調和級数
対象を一意に定める操作列を数え上げる
連結成分
グラフ問題
多項式・形式的冪級数
形式的冪級数の高等演算
橙色diff
結構いろんな考え方のできる問題! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…
AOJ
AOJ-ICPC1200点
JAG
順列
順列を写像と見る
順列を巡回群の直積と見る
DP
数え上げ問題
順列の数え上げ問題
操作列を数え上げる問題
式変形
最大公約数
逆順列を考える
整数問題
数珠
グルーピングの数え上げ
挿入DP
重複度で割る
第1種スターリング数
二項係数
コーナーケース
最小添字規則によってダブルカウントを防ぐ
グルーピング
競技数学色強め
AOJ-ICPC
JAG春冬コン
伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…