2020-09-24から1日間の記事一覧

2つの線分の交点の位置 ~ax + by = cと逆行列~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868625#1 解説 交差することは保証されている 線分を直線の式 ax + by = cで表す 交差するなら逆行列が存在するので求ま…

スライド最小値 Sliding Window Minimum Algorithm

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4867025#1 解説 蟻本p301にある 最初はmultisetを使ってO(NlogN)で解いたが、スライド最小値を使うとO(N)となる (N=10000…

AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4866924#1 解説 L個の条件について、条件iを実行後、条件jに遷移できるなら辺をはる。これはDAGになる そのDAG上の最小パス…