燃やす埋める問題の解説記事です

競技プログラミング 典型問題メモ 線形計画問題・整数計画問題に帰着される問題 Python高速化まとめ 数学メモ グリッドの最短経路の数え上げまとめ 特殊な形式的冪級数 燃やす埋める纏める ランダム生成まとめ

メモがてら書きます．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列を作る．各には個の選択肢があり，を選ぶとのコストがかかる．さらに，各についてのコストが追加でかかる．コストの総和の最小値を求めよ．解説複数の選択間にコスト…

形式的冪級数を用いた珍しい(と思った)解き方がある問題集 (解けなかったやつも載せる)厳密には形式的冪級数ではないもの(有理数の指数が出るもの)も載せてる．ABC221 H 解説とする． なのでDP遷移がわかって解ける．ABC222 H 解説であるので はの逆関数とな…

グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます．よくある書き込み(動的計画法)による解法は扱いません．目次 最短経路の数え上げとは 一般的な最短経路 ある点を通る最短経路 ある点を通らない最短経路 ある長方形領域を通…

競プロにおける数学関連のメモ

最終状態としてあり得るものの数え上げを行う問題をまとめる. 解法とかはあとでやる.目次 ARC108 D - AB ABC171 F - Strivore ABC156 E - Roaming ABC158 F - Removing Robots ARC110 E - Shorten ABC ARC107 C - Shuffle Permutation ARC108 D - AB ABC171 …

競プロ使うPythonのモジュールの使い方をメモしていきます. Counter(頻度分布) permutations(順列列挙) combinations(組合せ列挙) deque defaultdict(デフォルト辞書) Counter(頻度分布)リストや文字列を与えると要素ごとの出現頻度がわかる(辞書型みたいな…

競プロでのPythonはたとえ高速な(C++は通るような)アルゴリズムでも実装の仕方によってはTLEする(他の高速な言語に比べてしやすい). Pythonの高速化の方法について気づいたことをまとめていく. 関数化 リストの内包表記 MOD計算 deque タプル 参考 関数化な…

競技プログラミングにおける数え上げ問題とその解法をまとめます.

整数計画問題に帰着される問題を見つけ次第メモする. 何が変数かは察してください. 帰着されたからと言ってすぐ解けるわけではない． 整数計画問題はNP困難ではあるが，これらの問題から何か法則性を見つけて特殊な条件の整数計画問題を解く典型手法みたいな…

競技プログラミングにおける典型知識