プリム法ベースのシュタイナー木 - bowwowforeachの日記
AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
Dijkstra法に関するn考察 〜前半〜 - Mister雑記
(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。) 競技プログラミングのグラフ問題でしばしば題材となるアルゴリズム「Dijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。 そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。 目次 目次 Dijkstra法の概要 何をするアルゴリズムか 具体例 イメージ？ 実装方法 パターンA パターンB (PFS) 計算量の比較 問題例 後半について Dijkstra法の概要 何をするアルゴリズムか Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められる
Graph Golf参加記
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。 前提知識として知っておいてほしい単語は以下の2つくらいです。 グラフ(点と点が繋がってるアレのこと) 次数(頂点に繋がってる辺の本数のこと) 問題内容 自
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 - koyumeishiのブログ
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意されていた B問題 日本橋大渋滞 を解こうとしたのですが、実装が間に合わず未提出、0点のままコンテストは終了してしまいました。 後日考えていた方針の実装を終わらせ提出したところ、かなり出来のいい点数を出せたのでその振り返りをします。 2017/03/26 時点で一位 http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1176109 入力例2 74手 46555点 おおよその方針は次の一連のツイートの通りですが、もうちょいと詳しく解説。 天才過ぎて70手ぐらいまでにな
Trianguler
HCPC 勉強会 (2019/4/4) - Convex Hull Trick ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
蟻本P191 最大流 - 最小カット定理 - WARush
蟻本に載ってることそのまま書くだけ 蟻本の最大流で使われたグラフをそのままサンプルで使います。 ↓↓ グラフのカットとは、ある頂点集合Sに対して、Sから出ていく辺の集合の事をいい、 カット(S V/S)のように表します。また、その辺の容量の和をカットの容量といいます。 さらに、Sの中にsを、V/Sの中にtを含むようにカットすることを、 s-tカットといいます。 最小カット問題とは・・・ ネットワークにに対して、sからtへのパスが存在しなくなるために（つまりs-tカットで） 除去しなければいけない辺の容量の和の最小値はどれだけか という問題である。 フロー流量とカット容量の関係 まず、任意のs-tフロー f と任意のs-tカット(S, V/S)を考えてみましょう。 ↓こんなフローとカット↓ sについては( fの流量 ) = ( sから出る辺の流量 )であり、 それ以外のSの頂点vについては(
SRM580 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし
FrontPage - PukiWiki: 2012年度夏学期「実践的プログラミング」へようこそ
授業について 「実践的プログラミング」は教養学部前期課程で開講されている。全学自由研究ゼミナールです。 履修希望の方はUTAS等をご覧ください。2020年夏学期は月曜5限にオンラインで開講されました。 内容に興味がある方はPDFの資料等をご覧ください。(授業で扱う範囲はこの一部で、また細かくは差異があります) ウェブページについて 現在CMS変更に伴う更新作業中です。過去のページも引き続き閲覧可能です。 なお、国際大学対抗プログラミングコンテスト(ICPC)については、現在は多少状況が変化していますので、過去のページをご覧の際はご留意ください。 ACM-ICPCは、2018年12月までにはACMの後援が外れて、ICPCとなりました。 2020年度は、COVID-19の影響で、各チーム分散した環境で国内予選が行われています。教員による「監督」制度も適用されていません。 なお、来年度以降は未定
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サンタコンペで二度全完した話
ダイクストラ法典型問題集
WUPC2nd E問題