2019-05-01から1日間の記事一覧

最大全域木 Maximum spanning tree

Quiz https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_d Submit https://atcoder.jp/contests/iroha2019-day2/submissions/5220268 補足 普通必要とされるのは「最小」全域木です クラスカル法で最大全域木も求めることができます 方法は…

F - 総入れ替え

Quiz https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_f Submit https://atcoder.jp/contests/iroha2019-day2/submissions/5216485 解法 公式解説と違う解き方で解いたので書いておく まず、くじ引きはいつ引いても平等というのがある た…

最大流 max flow

使った問題 https://atcoder.jp/contests/soundhound2018/submissions/4578400 ライブラリ TODO 理解する方法 蟻本第二版 p188を読む プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作…

座標圧縮 Coordinate compression

方法 検索すれば豊富に見つかる 使いどころ 座標の範囲が109などで走査したらTLEする 一方で座標データ数が105などで座標圧縮したら間に合う 要素 配列・ソート 二分探索, lower_bound それを使う問題たち Manhattan Crepe Cart (Google Code Jam) https://c…

線分の交差判定 c++ Judgment of intersection of line segments

http://perogram.hateblo.jp/entry/abc016_4 この記事を関数として切り出した。 関数 // 交差判定セット typedef complex<double> C; double cross(C a, C b){ return a.real() * b.imag() - a.imag() * b.real(); } // ベクトル p0->p1, q0->q1 bool is_intersect(C</double>…