最小全域木

問題 https://codeforces.com/contest/1849/problem/F (diff 2700) 非負整数の集合に対して、のスコアをの相異なる二要素のxorとしてあり得る最小値とする。ただし、の場合スコアはとする。 相異なる個の整数を与える。二つの空集合を用意し、各をどちらか片方に挿入する。としてあり得る最大値を達成する操作方法を一つ求めよ 制約 TL7.5秒

すっかり作問のことも落ちている昨今。 今月は３連続ARC＋AGCという黄橙がまぁまぁ忙しい期間ともなり地味に2年ぶりにレートがHighest更新しました。いや、もう無理だろうなーと思ってたんですがそんなことないんですね。

今日やったこと ALDS1_12_A Minimum Spanning Tree https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A みなさんご存じプリム法ですね 私は知らないです 任意に選んだ始点から行くことのできる節点の中で、一番重みが少ない節点に行く だったかな あまり詳しくは覚えていない 本当に任意の始点から始めても同じなのか試したら同じだった プリムさんすごい まだ木構造を完全に理解しているわけではないので解像度を上げたい ちなみに自力で書こうとしたら答えがオーバーフロウしました だめだね ダイク…

備忘録最小全域木は、重み付きグラフなどにおいて、連結なグラフにするために最小で重みがいくつになるかです（日本語変かも）。大きくクラスカル法とプリム法がありますが、ぼくはプリム法の方で実装しました（一般的にはクラスカル法のほうがシンプルなので使われている）。 実装 int purimu(int n,int m,vector<vector<vector<int>>>rotti) { //二次元配列の中身は{行く頂点、距離} priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>prq; //優先度つきキューの中身は{…

01/01(月) 午前10時に親に起こされた。家族はみんなすでに朝食を終えたらしく、一人でお雑煮とおせちを食べた。すぐ着替えて初詣に出発。 今年の神社は雪がまったく積もっておらず新年という感じがしない。普段は駐車場の端に雪が山盛りになっていて車は2列で駐められているのだが、今年はなんと3列形成されていた。また出店が1店しか出ておらず寂しい感じ。 初詣 今年雪全然ないね pic.twitter.com/kUjqDBGRaH— こたつがめ (@kotatsugame_t) 2024年1月1日 昼食を摂って午後3時頃帰宅。両親は買い物に出かけ、自分含む残った3人はこたつで昼寝の体勢に入った。 午後4…

こんにちは。リユナと申します。今日は北朝鮮の競プロについて書きますね。 こんなICPCは嫌！ 0.概要 1.問題 問題1. 配列転倒数 問題2. B＿N 問題3. 行列検査 問題4. リンゴ配り 問題5. 易い幾何問題 問題6. 最良の経路探し 問題7. 良い日々 問題8. ヒョソンとクァンソン 問題9. 国際網奉仕 問題10. 宝箱 問題11. K番目のグラフ切断*4 問題12. 長い整数の因数分解 2. 翻訳後記・感想 0.概要 始める前に、標記について言及しておきます。普通韓国では北朝鮮のことを「北韓」だと呼びます。韓国の北側っていう意味で、北側の政権を正式的に認定しない態度が入ってます…

先日行われたHACK TO THE FUTURE 2024 (AtCoder Heuristic Contest 027)でHeristicレーティング黄色になりました！ … Algo入青から2年半ぶりに新しい色に到達できたのでうれしいです。 ヒュの色変記事ってあんまり見たことないので書いてみようかなと思ったんですが、何書けばいいのかわからなかったので、今までのAHCを自分なりに振り返ってみようかなと思います。記憶とツイートが頼りなので嘘を書いてたらすみません。 注意！ 以下、AHC過去問のネタバレが大量に含まれます Introduction to Heuristics Contest - A…

全体の進捗 やった回: ABC328 成績: ABCD4完 / 1ペナ(+未AC1ペナ) / 37:36(ペナ込み) 推定パフォーマンス: 980 松江のホテルで力尽きていて参加できなかったABC328を、Rails Girlsの競プロ同好会でセルフ実況しながらバチャりました。自分が解きながらだったのでかなり駆け足の解説になりましたが、お付き合いいただきありがとうございました！ 推定パフォーマンスを見た感じまずまずの結果*1というところですかね、早解き回ではあったのかも。E問題は終了間際にガラッと方針転換して結局間に合わなかったけど解説読まずには解けたので、うーん、でも時間内に解きたかったなぁ…

アルゴリズムとデータ構造にもう少し強くなりたく「アルゴリズム実技検定」という資格の公式テキストを読んでみました。 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 = …

ITエンジニアのための転職・就職支援サービスである「paiza」が提供している、プログラミング教育コンテンツ「paizaラーニング」中の「レベルアップ問題集」に「Union-find・クラスカル法メニュー」というのがある。 「クラスカル法」というのは、グラフ・ネットワーク系の問題である「最小全域木問題」を解くためのアルゴリズムの1つで、「最小全域木」なんて専門用語を見るとビビッちゃうけれども、やっていること自体は意外と簡単。クラスカル法そのものよりも、クラスカル法で用いる「ユニオンファインド」というアルゴリズムの方が少し難しい。 「クラスカル法はユニオンファインドを用いる」と言うよりも、「ユニ…