Hatena Blog Tags
はてなブログ トップ
連結成分
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

連結成分

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
競技プログラミング日記•2年前

AtCoder Beginner Contest 304E

ABC304E クエリ問題で，一つのクエリにつき高速に求める． 良いグラフの定義通りだと，全ての\(i \in K\)に対して調べることになるが， クエリでは1本しか辺を追加しないので，変化は少ない． クエリ毎に共通して使える部分が多くあるので，そこを前処理しておく． 良いグラフか判定する際，連結成分毎に考えれば良い． 各連結成分ごとに\(x_{i}, y_{i}\)が含まれているかが重要で， それ以外はグラフの形は影響しない．クエリで調べたいことは，異なる連結成分2つが与えられたとき， それを結んで良いかどうか．これを前処理する． あとは\(O(N), O(Nlog N)\)(または\(N\…

#AtCoder#AtCoder Beginner Contest#query#連結成分#グラフ

関連ブログ

kotatsugameの日記•3日前

週記（2024/12/23-2024/12/29）

12/23(月) 午後4時前起床。今日のインターン先定例会は年末だからか知らないが縮小版で、30分遅く始まり、しかもほぼ勉強会のみだった。 内容はAHC040の話。箱を詰めるとき斜めのラインで置いていくと良いという話で、ゲーム「2048」を思い出した。あれも、例えば左と上でばっかり操作して大きな数を斜めに作っていくのが良い。 そのあとは日付が変わるまで先週の週記を書いていた。ICPC部分は真っ先に、結構気合いを入れて書き上げた。作業量の観点から、後日そこだけ切り出して独立した参加記にする、ということはしないだろう。常体を敬体にするのが結構な手間。 ほんの少しの穴あきを残して投稿。それからはうっ…

獅子座じゃない人のブログ•5日前

AtCoder Beginner Contest 386 (ABC386) G - Many MSTの勉強

問題G - Many MST解法Editorial - AtCoder Beginner Contest 386kyopro_friendsさんのユーザ解説の方法で解く。 ユーザ解説同様、問題文中の を でおき直す。無向グラフ の連結成分数を とする。 また、全ての辺の重みが 以上 以下の整数である頂点ラベル付き完全グラフ全体の集合を とする。 について、辺の重みが より大きい辺のみを全て削除したグラフを とおく。 についてのクラスカル法を考えると、辺の重みが 以下である辺について処理を終えた時点のグラフの連結成分数は、 と等しいことがわかる。 の最小全域木の辺の重みの総和は で表せることもわ…

kmjp's blog•5日前

Codeforces #959 : D. Funny Game

中盤で失速した回。 https://codeforces.com/contest/1994/problem/D

zawatinはてなブログ•10日前

ICPC2024 Asia Yokohama Regional 参加記 (Spinning-akabeko zawatin)

はじめに 自己紹介、チームメイト紹介 day1 day2: コンテスト 来年に向けての反省 複数人で考察を行う 問題文の共有の工夫 提出前確認の徹底 祈る day2: 懇親会 おわりに はじめに ICPC 2024 Asia Yokohama Regional に参加させていただきました。はじめに、運営にかかわっていた皆さん、すばらしい大会をありがとうございました！月並みですが、1年間の集大成を発揮するガチンコ勝負、めちゃくちゃ楽しかったです。 現在私は学部4年で、卒論執筆で忙しく本来参加記を書かない予定でしたが、少し区切りがついて時間の余裕ができたのでとり急いで書くことにしました。大会ではあ…

kotatsugameの日記•10日前

週記（2024/12/16-2024/12/22）

12/16(月) 午後3時過ぎ起床。半からインターン先定例会に出た。 先週は1on1でタスクをいただいたのみで、まだ稼働できていない。勉強会は遅延セグ木＋AVL木で要素の挿入・削除操作を可能にするという話だった。すごい木を使う問題はUniversal Cupでたまに見かけるが、いつもNyaanさんにぶん投げて終わってしまう。 解散後に追加で1時間ほど1on1。別のタスクが降ってきた。数学的なことをやってほしいという感じだったが、専門が違いすぎてもう何にもわからない……。やるだけやってみようとは思う。 あとは週記を書いて、午後11時半くらいに投稿。全部書ききることができた。それから朝まで、本を2…

けんちょんの競プロ精進記録•11日前

AOJ 1455 Ribbon on the Christmas Present (ICPC アジア 2024 A)

制約的に でも通るが、スタックを用いて でも解ける！ 問題へのリンク（仮） 問題概要 マスからなるマス目があり、最初各マスには 0 が書かれている。このマス目に対して、以下の操作を行う。 正の整数値 と、連続するいくつかのマスを選ぶ（ただし、どのマスに書かれた数値も 以下でなければならない） これらのマスに対して、その値が より小さいならば、 に書き換える 操作を繰り返すことにより、各マスの数値が となるようにしたい。これを実現するための操作回数の最小値を求めよ。 制約 考えたこと 基本的には、 の中に含まれる整数値のうち、小さい整数値から順に書き込んでいけばよいと考えた。その際に、すでに「よ…

kotatsugameの日記•17日前

週記（2024/12/09-2024/12/15）

12/09(月) 午後1時半起床。定例会が始まる前に学食に行って食事し、購買でラノベを買って帰ってきた。 午後3時半からインターン先定例会に出席。ウズベキスタンから無事帰ってきたと報告した。今週からまた1on1を入れてもらい、少しでも稼働していく所存。勉強会はジップの法則の一般化であるべき乗則について。Barabási–Albert modelという、次数分布がべき乗則に従うランダムグラフ生成モデルを知った。 解散後は週記を書いていたが、実質二日ちょっとしかないのでUniversal Cup以外を早々に書き終え、それからはYandex Cupの参加記のほうを書き進めていた。そちらは完成までまだ…

プログラム系統備忘録ブログ•18日前

TSG CTF 2024 write-up (Reversingジャンル全問)

TSG CTF 2024へ参加しました。そのwrite-up記事です。

kmjp's blog•21日前

Codeforces #953 : Div2 F. Large Graph

よくこういう問題思いつくな。 https://codeforces.com/contest/1978/problem/F

kmjp's blog•21日前

yukicoder : No.2983 Christmas Color Grid (Advent Calender ver.)

このタイプのDFS初めて。 https://yukicoder.me/problems/no/2983

KADOKAWA Connected Engineering Blog•23日前

Amazon MWAA + Step Functions (+ Snowflake × dbt) による大規模データパイプライン構築事例紹介

KADOKAWA デジタル戦略局 グループデータマネジメント部（出向）の中野 (takamoto) です。 足掛け2年半の ADR 活用事例紹介 〜 ADR から始める設計ドキュメント改善 - KADOKAWA Connected Engineering Blog などの過去記事から所属は変化していますが、変わらずデータプラットフォーム上のデータパイプラインの開発・運用を主に担当しています。 私の所属しているチームでは データプラットフォーム統合プロジェクトの紹介 - KADOKAWA Connected Engineering Blog で紹介している Snowflake 環境上に構築された…

kmjp's blog•24日前

Codeforces Global Round 26 : E. Shuffle

コードは短いんだよな。 https://codeforces.com/contest/1984/problem/E

ブログ名•24日前

3 種類の強連結成分分解アルゴリズムや、そのバリエーションの速度比較

概要 LIbrary Checker のジャッジをお借りして、次の 3 種類の強連結成分分解アルゴリズムそれぞれの、いくつかのバージョンの速度を比較します。 Kosaraju's algorithm Tarjan's algorithm Gabow's algorithm その結果、Vec<Vec<usize>> を構築して行う Kosaraju's algorithm は、この記事の最速実装に比べて $3$ 倍程度遅いことがわかりました。 今回の計測では最速の座は Gabow's が手にしましたが、Kosaraju's の高速な実装もそれとほぼ変わりませんでした。従って実装の短さを考えると …

kotatsugameの日記•24日前

週記（2024/12/02-2024/12/08）

Yandex Cup参加記、書いてます。本当です。現在1万字強。 12/02(月) 12/03(火) 12/04(水) 12/05(木) 12/06(金) 午後3時過ぎに自宅到着。MHC Tシャツが届いていた。 pic.twitter.com/jwKnxWYwJW— こたつがめ (@kotatsugame_t) 2024年12月6日 機内で横になれたからか思ったより眠くない。手っ取り早く荷解きを済ませ、シャワーを浴びて洗濯まで行った。自宅最寄り駅から濡れた落ち葉でいっぱいの路面を転がしてきたスーツケースの車輪が大変なことになっており、その掃除が一番大変だった。 家族LINEに帰宅報告をし、流れ…

KCPCブログ•1ヶ月前

【ABC383】ただいま水色！ 【KCPCブログ】

こんにちは、KCPC のkmmtkm です！今回水色に帰ってくることができました！！嬉しい！！ というわけで早速ABC383 の参加記を書いていきます。 目次 目次 ABC383 A問題 B問題 C問題 D問題 E問題 F問題 コンテスト後 コンテスト結果 ABC383 今回のABC383、X では賞金のことが話題になっていた気がします。「3完以上した人から70人に1万円」という珍しいタイプの回でした。 3完という条件がなんとも絶妙なラインですね。そんな中、今回の配点は 150-250-350-400-500-525-625 です。「3完」がいつもよりは厳しく設定されている雰囲気が出ています。…