読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

天下一2015予選A D - ハシポン

1週間かけてAC。 問題 D: ハシポン - 天下一プログラマーコンテスト2015予選A | AtCoder 連結な単純無向グラフ が与えられる。 にいくつかの辺を加えた が橋をちょうど1つ持つ連結な単純無向グラフとなるには、最小何本の辺を追加すればよいか? 不可能な場…

ARC056 B - 駐車場

問題 N 人の人が 1 番目から順に駐車場にやってくる。駐車場は N 個の駐車スペースが無向辺で結ばれたグラフで表され、入り口は頂点 S である。i 番目の人は i 番目の駐車スペースに車を停めるか、停められないならば停めずに帰る。 駐車できる人の番号をす…

ABC014 D - 閉路

どこからLCAなんて発想が出てくるの!?と思った人用。 問題 木に辺を追加したときの閉路長を各クエリに対して求めよ。 制約 頂点数: クエリ数: 解法 辺 を追加したときの閉路長は、もとのグラフにおける点 と点 との最短距離を とすると、 (追加する辺の長…

SRM682 Div.1 Easy SmilesTheFriendshipUnicorn

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14104 グラフ上にfriendship chainが存在するか判定せよ。ただしfriendship chainとは、異なる点A, B, C, D, Eに対し、AとB, BとC, CとD, DとEがそれぞれ隣接するようなグラフのことである…

ABC022 C - Blue Bird

想定解と違うっぽかったので書いておきます。(ダイクストラで解いた) 問題 abc022.contest.atcoder.jp グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

【グラフアルゴリズムとその例題】蟻本 2-5章 まとめ

蟻本 2-5章 のまとめです。各グラフアルゴリズムの概要と例題について。例題は一応ソースコードもつけておきます。 アルゴリズム 最短路問題 ベルマンフォード法 単一始点から他の各点への最短路を求める。負の長さの辺があってもOK。負閉路を持たない場合は…

ダイクストラ法とその例題

ダイクストラ法とその例題についてまとめておきます。 例題はワーシャルフロイドのやつ使いまわしです(ダイクストラ向きのは二分探索とか絡んで難しいので……) ダイクストラ法とは? ダイクストラ法(Dijkstra's algorithm)は、グラフのある点から各点までの…

ワーシャルフロイド法とその例題

ワーシャルフロイド法のアルゴリズムと例題についてまとめておきます。師匠へのレポートもかねて。 ワーシャルフロイド法とは? ワーシャルフロイド法(Warshall–Floyd Algorithm)とは、グラフの全点間の最短距離を求めるアルゴリズムです。簡単な3重ループを…

Codeforces Round #338 (Div. 2) B - Longtail Hedgehog

過去問再挑戦キャンペーン実施中。 問題 1からnまでの番号がつけられた点とm個の辺からなるグラフがある。重複辺・自己辺はない。 このグラフのいくつかの辺に色を塗ることでハリネズミを作る。ハリネズミは「尾」と「背骨」からなる。これらは以下のように…

square869120Contest #1 C - お金の街 (The Money Town)

問題 C: お金の街 (The Money Town) - square869120Contest #1 | AtCoder 街i(i = 1..n)にDi円落ちている。同じ街を2度通らないように進むとき、拾えるお金の最大値はいくらか、という問題。 解法 DFS。お金の最大値は逆順に求まる(コード参照)。 def dfs(i)…

ABC016 C - 友達の友達

問題 C: 友達の友達 - AtCoder Beginner Contest 016 | AtCoder 友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は、「友達の友達」に含みません。 解法 グラフの問題。 入力から隣接リストを作る。 ユ…