競技プログラミングにハマるプログラマのスレ 259 (1002ﾚｽ)
上下前次1-新

---

このｽﾚｯﾄﾞは1000を超えました｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ

---

120: 11/22(土)22:45 AA×


[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
120: [sage] 2025/11/22(土) 22:45:20.45 Gemini 3 Pro 賢すぎる、瞬殺 # F 数字のペア (d, d+1) ごとに独立に考えられます (d=0...8)。 各ペアについて、元の文字列から d と d+1 のみを抽出した列を考えます。 条件を満たす部分列は、「ある d を最後の d として選び、その左にある d と右にある d+1 から適切に選ぶ」ことと対応します。 この d より左にある d の数を x、右にある d+1 の数を K とすると、寄与分は C(x+K, x+1) となります。 これをすべてのペア、すべての d の位置について足し合わせることで O(|S|) で解けます。 # G S の Suffix Automaton (SAM) を構築します。SAM は S の全ての部分文字列を O(|S|) のノード数で表現する DAG です。 この DAG 上で「移動できなくなった方が負け」というゲームを行います。 各ノードについて、遷移先に「負け状態」が一つでもあれば、そのノードは「勝ち状態」となります。 SAM のノードを文字列長が長い順（DAG のトポロジカル逆順）に走査し、勝敗を確定させていくことで、根ノードの勝敗を O(|S|) で判定できます。 http://medaka.5ch.net/test/read.cgi/prog/1763744158/120
賢すぎる瞬殺 数字のペア ごとに独立に考えられます 各ペアについて元の文字列から と のみを抽出した列を考えます 条件を満たす部分列はある を最後の として選びその左にある と右にある から適切に選ぶことと対応します この より左にある の数を 右にある の数を とすると寄与分は となります これをすべてのペアすべての の位置について足し合わせることで で解けます の を構築します は の全ての部分文字列を のノード数で表現する です この 上で移動できなくなった方が負けというゲームを行います 各ノードについて遷移先に負け状態が一つでもあればそのノードは勝ち状態となります のノードを文字列長が長い順 のトポロジカル逆順に走査し勝敗を確定させていくことで根ノードの勝敗を で判定できます

---

上下前次1-新書関写板覧索設栞歴

---

あと 882 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ

---

ぬこの手 ぬこTOP 0.909s*