Study [C++]n個をm人に配分するときの組み合わせを全列挙する(競プロ)
数学では重複組み合わせ問題とも呼ばれるらしい.
背景
この問題の回答テクニックの中に, 「_を文字列と文字列の間に入れる組み合わせを全列挙する」というものがあった.
公式解説ではDFSを使っているが, 再帰ではな...
Study
Study Study 切り下げ?切り上げ?オーバーフローを避ける不等号の演算(c++)
atcoderの整数の掛け算で、オーバーフローを避けるため、代わりに割り算を使用する事がある。
不等号がついている式で演算を行う際に、小数点を切り捨てか、切り上げかわからなくなったのでメモ。
問題
\(a \ti...
Study 凸包を求めるC++プログラムとテストケース(Graham)
授業のレポートでせっかく作ったので公開する。
グラハムのアルゴリズムで凸包を求めるC++プログラム
#include<bits/stdc++.h>
#define rep(x,y) for(int x=0;x<...
Study 試行回数の期待値は確率の逆数？ABC194Dの解説と考え方
問題
ABC194のD問題
n個の頂点のグラフがあり、最初は頂点1にいる。一回の試行でランダムに頂点を選び連結にしていく。すべての頂点を連結にするときの、試行回数の期待値を求める。
つまり、頂点すべてを一...
Study ダイクストラ法の計算量をわかりやすく
個人的備忘録
辺の数を\(E\),頂点の数を\(V\)とする。 スタート地点とゴール地点は固定されている。
オリジナル
vectorなどの配列のみで実装した場合
$$\mathcal{O} (V^2 + E...
Study x + y = k となるx, yの場合の数
本来解きたかったのはAtCoderのこの問題です。
解説PDFもYouTube解説もありますが、基礎というか前半部分で実装するx + y =kは頻出かなと思ったのでメモを残します。
問題文
\(x, y,...
Study LU分解
LU分解をわかりやすく具体例を使って解説しました。教科書やインターネットで探しても数式ばっかでよくわかんなかったので忘れたとき用自分メモ。あとMathJax-LaTeXプラグインをいれたからその実験も兼ねてる