Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

解説

グラフの橋と関節点の効率的な判定LowLink法の解説

LowLinkを実装してみた。自分用の詰まった部分のメモも含む。 どういう問題をやるの グラフが与えられて 関節点 その点を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる) 橋 その辺を取ってしまうと、グラフの連結成分は増えてしまう(バラ…

けんちょんさんの中国剰余定理の補足

先日のABCで中国剰余定理による連立合同式が出たことでまた冷えたのでこれをきっかけに中国剰余定理を勉強しました。

NTT(数論変換)のやさしい解説

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何? とかについてもこれを…

ABC169 - F - Knapsack for All Subsets

F - Knapsack for All SubsetsABC実質初全完を祝って解説記事。 概要 長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。 f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とす…

競プロ界隈用語の(自分向け)解説

競プロ界隈の独特な雰囲気を醸し出す用語たちを独断と偏見で解説する。 #競プロの闇 何かあったら@nonpro3 までご一報ください。 あ行 う 笑[名] 「う し た ぷ に き あ 王 国 笑」の省略版。どうみても「笑う」のアナグラムだけど王国民には国名の略称に見…

MIS.W新歓コンテスト2020 - SABAKAN FEVER

www.hackerrank.com 概要 解法 パズル 海辺の20以上の4区(渋谷、新宿、千代田、中央)は1つしか使わない 端から攻めるがほとんど通用しない 頭を抱えたくなる局所最適解 強烈に自己主張されてる港区は使わない 全探索 BitDP 実装 統計&講評 最後に 概要 東京…

有向グラフの最短路と最長路問題

有向グラフの最短距離は、 負の辺が存在しないのならば、「ダイクストラ法」 負の辺が存在するならば、「ベルマンフォード法」、「ワーシャルフロイド法」 がこれを求めるアルゴリズムとして知られていて、そのうち、「ダイクストラ法」がこの3つの中で唯一E…

【競プロ】すべての行and列が○○を満たす行列を構築シリーズの典型?要素

突然ですが次のタイプの問題、見おぼえありますか? N*Nの行列がある。すべての行と列において、○○という条件を満たす(もしくは行が○○という条件、列が××という条件を満たす)ように、そのN*Nの行列を構築せよ。構築不能なら-1を出力せよ。 トラウマ要素重め…

(形式的)べき級数と数え上げの写像12相との関係性 後編

前編の読了お疲れさまでした。形式的べき級数でいくつかの数え上げを解決して、残るは数え上げの難関の3つの数(僕呼び)の、スターリング数、ベル数、分割数のみです。この三つの数はいずれも一般的な場合では漸化式を使わない式で表せません。今回の記事では…

(形式的)べき級数と数え上げの写像12相との関係性 前編

先日、競プロやってたらhotmanから「形式的べき級数と数え上げの相性が抜群すぎてつながってて気持ちいい、世の中の眠る真理が目覚めた気がする」といわれて、気になったのでまとめた。 この記事は、数学的厳密性に欠けています。多くの変形が厳密な確認をな…

コスト0辺のテクニック

この記事は、競技プログラミングでよくあるグラフの問題で、愚直に問題文の指示通りやると辺の数があまりにも多くなりすぎるようなものに対して、コスト0の辺をうまく利用することで辺の数のオーダーを落とす者である。 性質上、すべてのものに適応できるわ…

いくつかの要素を抜くDP No Needから考える

atcoder.jpこの問題から、次のような一般化された問題を考える。 問題文 N個のものを考える。高速でそのうちの1つを抜いた時の計算結果を求める。