こんにちは。
Atcoderを初めて1.5ヶ月緑コーダーのうなぎです。
ここでは自分が勉強して分かり易かった記事などをまとめていこうと思います。世の中には竸プロ強者によるわかりやすい記事がありふれているので、わかりやすさや説得性を求めている人はそちらをご覧になることをおすすめします。
あくまで、初心者が初心者の時に感じたことを書いている記事となっています。
分かりやすかった記事
最適化基礎第八回最小全域木問題
東工大の講義資料。講義資料だけあって証明がしっかり書いてある。細かいことを気にしない人でも軽く目を通すといい気がする。
最小全域木と最大流問題
落合秀也さんのスライド。プリム法が図で示されているので、直感的に理解しやすい。おすすめ。
最小全域木問題
プリム法がどのように実装されるかについてのアニメーションがある（すごい！！）。
解いた問題
@e869120 さんの作成されたレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の該当問題(64-67)を2020年8月時点でレート900の私が解いた感想です（あくまで感想です、いかに述べる解き方などが最適解とは限りません）。
一緒に精進する人にとってのモチベーションになれば幸いです。
以下該当問題を解いた感想（ネタバレ注意）
GRL_2_A - 最小全域木
heapq使って解いてみた。最小全域木がいかなるものか分かっていれば解ける。
JOI 2010 春合宿 - Finals
prim heapを使用することで解ける。題意をprim heapで解けることと結び付けられるか。
AOJ 1127 - Building a Space Station
それぞれの宇宙ステーションの半径と距離の比較にやや工夫がいるだけで、あとはprim heap。(解法のメモ)
AtCoder Beginner Contest 065 D - Built?
x,yを独立に考えることに気付けるかどうか。
感想
$O(V^2)$と$O(|E|\log|V|)$の計算量の違いには気をつけた方がいいのかな。どちらかしか知らないと間に合わないことがありそうでいつかそういった問題に当たりそう。