最小全域木

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)に参加しました。 結果 A,B,C,Dの4問正解でした。 E問題は単純な最小全域木を求める問題だと思って解いてたけど勘違いしてた。 勘違いに気づいたのが残り5分のところで、どうにか対応させられないかと考えたけど5分じゃ無理だった。 A - Not Too Hard 問題文のとおりに処理して答える問題。 数値を受け取ってX以下なら合計に加えて、という処理をN回繰り返して最後に合計を出力すれば解ける。 数値の入力とif文、数値の加算と標準出力ができれば解ける問題。 B - 11/11 月日が…

アルゴリズムとデータ構造にもう少し強くなりたく「アルゴリズム実技検定」という資格の公式テキストを読んでみました。 book.mynavi.jp 競技プログラミングで有名なAtCoderの会社が運営してる資格試験らしいです。資格を取る気は現状ないですが教材としてはよかった。 アルゴリズム実技検定に始まってサンプルコードに使われているPythonの紹介が入りその後、サンプル問題を解きながら競技プログラミングのテクニックを学んでいく構成です。 サンプルコードは個人的には静的型付け言語の方が読みやすいと思うんでPythonだと複雑なデータ構造になった時たまに辛く感じることは正直あったりもしましたが解説…

プリム法と同様に、重み付き無向グラフにおいて最小全域木を求めるアルゴリズムである。 クラスカル法とは 以下のアルゴリズムである。 辺集合Eを重みの小さな順にsortする。 その辺を追加しても閉路ができないのであれば、その辺を答えに追加する。この閉路判定はunion-findなどを使えばより簡単に求めることができる。 証明 これによってできる木はプリム法で構成される木と同じであることが明らか。（暇がある時に追記します） 実装 やってないです。union-findを作ってから書きます。arc076-dとか。

プリム法とは、クラスカル法と同様に重み付き無向グラフにおいて最小全域木（とその辺の重みの総和）を求めるアルゴリズムである。 プリム法とは ある頂点を一つ選ぶ。 確定している頂点から確定していない頂点への辺のうち、重みが最も小さなものを通る辺としてその確定していない頂点を確定させる。 2を確定していない頂点が無くなるまで続ける。 証明 貪欲法に似ていて、実際に他の方法があるとして矛盾を導くことができる。 実装 let mut used = vec![false; n]; let mut h = std::collections::BinaryHeap::new(); let mut ans = …

問題 コストCnのN個中から好きなだけ選んで要素K個を全てP以上にする時の最小コストを求める問題 (0<N<100,1<K,P<=5) 考えたこと Nが100なのでNの3乗の解の可能性を考える。また、最小コストを求めよということで最小全域木の問題にできないかと考える。スコア毎に0-5として、あるiを採用したら、そのスコアに移動できるような有効グラフを考えるも、いつそのiが採用されるかわからないため、グラフの本数がとても多くなることに気づき、やめる。次に、各iを全てpriority_queueに入れて、小さい順から選択し、別のjを足し合わせてまたpriority_queueに入れるという方針が思…

｜アルゴリズム １．アルゴリズムとは ２．アルゴリズムの特性 ３．アルゴリズムの重要性 ４．アルゴリズムの種類 ５．アルゴリズムの評価 ｜アルゴリズムの基本「制御構造」 １．順次構造 ２．選択構造 ３．繰り返し構造 ｜アルゴリズムと流れ図（問題解決の道しるべ） １．端子 (Terminal) ２．処理 (Process) ３．定義済み処理 (Predefined Process) ４．判断 (Decision) ５．入出力 (Input/Output) ｜アルゴリズムと繰り返し制御（ループ） １．繰り返し制御（ループ）の重要性 ２．ループの種類 ｜アルゴリズムの効率性 ｜アルゴリズムの設計 A…

ここ最近のやつ E - Add and Mex 結局0~200000までになる数はAiにiを加算より、iが大きくなると適する数がどんどん減って2000000くらいで済むやつ。思いつかなかった。 E - Notebook 根付き木の構築として考えればよかったが、気づかなかった。 ADDとかDELETEから頂点のことだと思えばよかったのか？ E - MST + 1 頂点1から最小全域木を作って、そのクエリの辺が追加されるのと最小全域木上でクエリの辺が結ぶ頂点がつながるの、どっちが先かな〜をしようとしたが、これだと3個以上の頂点を含むサイクルで他に辺がない場合のケースを考えられないので、全ての頂点か…

ちょっといまいちだった回。 https://codeforces.com/contest/1726/problem/D

また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張る こうしてできる辺数 のグラフにおいて、最小全域木の重みを求めよ。 制約 考えたこと Kruskal 法をやるのには違いない。というわけで、 の値が小さい順に処理していく。 このとき、たとえば と が互いに素ならば、もうコスト の辺だけで MST が作れる。 一般には としたとき、たとえ 辺すべて結んだとしても、 個の連結成分に分かれるこ…

最近話題の Functional Graph の問題！ 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャンディーを配る順序を最適化することで、不満度の最小値を求めよ。 制約 考えたこと 問題文を一目見ただけでも、いくつかの典型要素がある。 Functional Graph であること (各頂点につき、辺が 1 本だけ出ているグラフ) 順列を最適化する系の問題であること 後者の要素がある分、他の Functional Graph の…

はじめに この記事でやること 注意点 （前半）マトロイドと貪欲法 マトロイドの定義 【定義 1.1.1】*2 マトロイドに関する用語 【定義 1.2.1】 【定義 1.2.2】 【定義 1.2.3】 【定義 1.2.4】 【命題 1.2.5】*3 マトロイドと貪欲法 【定義 1.3.1】 【定義 1.3.2】 【定義 1.3.3】 【定義 1.3.4】 【定理 1.3.5】 【定理 1.3.6】 【定理 1.3.5】の証明 【補題 1.4.1】 【定理 1.3.6】の証明 【補題 1.4.2】 （後半）マトロイドのクラスカル法への適用 ベクトルマトロイド 【命題 2.1.1】 グラフのマトロイ…

Bまで簡単でCから難しかった回。 https://codeforces.com/contest/1687/problem/B