先日、こんな記事を書いた。 拡張ユークリッドの互除法を自己流で実装してみた。 - いろはすの競プロ反省会 これだけではあまりに不親切なので、ここに書いたコードの解説をしていこうと思う。 ※上の記事に書いたコードは自己流で書いたものなので、蟻本に載…

結論から言えば、自分の中ではかなり力が出せたコンテストだったと思う。 少し手間取ったところもあったがA~Cまではほぼ順調にACし、残り５０分強を残してD問題に進むことが出来た。 時間としてはかなりあったが、やはり今の自分の実力では最後のD問題を通す…

蟻本を読みながらけんちょんさんの記事に載っている問題を毎日解いているが、LISの項でこの問題が分からず、やむを得ず他の人の解答を見たときに学んだことが多かったのでメモ。 ・upper_boundではなくlower_boundを使う ・答えの探し方(lower_bound使う) ・…

蟻本を読んでいたら、クラスカル法の正当性の証明が省略されていたので、自分で証明を構築してみた。 誰かの役に立つといいな。 ちなみにTeXで書く元気はなかった。汚くてごめんなさい。 クラスカル法の正当性の証明 連結な無向グラフG上のクラスカル法を考…

何番煎じか分からないけどやってみた。 （蟻本だとクラスや構造体にまとめてなくてとっ散らかってたため） #include<bits/stdc++.h> using namespace std; struct union_find{ vector<int> par; vector<int> rank; union_find(int n){ rank = vector<int>(n,0); for(int i=0; i</int></int></int></bits/stdc++.h>