けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

グラフ問題

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

AtCoder ABC 131 F - Must Be Rectangular! (600 点)

なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…

AtCoder ABC 131 E - Friendships (500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…

CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

AOJ 3048 Averaging (AUPC 2018 day2-J)

二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

AtCoder ARC 101 E - Ribbons on Tree (900 点)

すごく典型的な「二乗の木 DP」!!!!! そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…

SoundHound 2018 予選 C - 広告 (400 点)

ちょっと話題になった超典型フロー 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいです。 各マスに 1 個のみ コマを置けるのは白いマスのみ 隣り合う白マスの双方にコマを置く…

diverta 2019_2 F - Diverta City (900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

AtCoder ABC 126 D - Even Relation (400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder AGC 001 D - Arrays and Palindrome (1000 点)

楽しかった。 回文系の問題。「〜な条件だと結局全部一緒になる」という問題の雰囲気がどことなく数オリっぽい。 必要条件を頑張って列挙したら実は十分な感じもまた、数オリっぽさと AGC っぽさの両方がある感じ。 問題へのリンク 問題概要 総和が 、長さが…

diverta 2019 F - Edge Ordering (1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

AtCoder AGC 033 C - Removing Coins (800 点)

これ大好き!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…

AtCoder AGC 032 D - Rotation Sort (1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

Codeforces 554 DIV2 D. Neko and Aki's Prank (R2000)

こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…

GCJ 2019 Qual B - You Can Go Your Own Way

ちょっと考えればできる 問題へのリンク 問題概要 × のグリッドグラフの左上から右下への最短路が 1 つ与えられる。この最短路と辺を共有しない最短路を一つ求めよ (頂点で重なるのは OK) 制約 考えたこと 対角線に沿って反転すれば OK #include <iostream> #include <sstream> </sstream></iostream>…

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

Mujin 2018 D - うほょじご (400 点)

いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気 atcoder.jp 問題概要 正の整数 に対し、 で を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 が与えられる。 なる整数の組 であっ…

AtCoder AGC 032 C - Three Circuits (800 点)

見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…

AtCoder AGC 032 B - Balanced Neighbors (700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!! 問題へのリンク 問題概要 頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ: どの頂点についても、その頂点に隣接している頂点の番号の和が等しい 制…

AOJ 2935 赤黒そーるじぇむ (RUPC 2019 day3-F)

楽しい!!!好き!!! 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…

AOJ 2386 Sightseeing Tour (AOJ-ICPC 250 点)

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね!!! その証明はすごく楽しいと思う!!! 問題へのリンク 問題概要 頂点数 の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して 頂点 i から頂点 j …

AOJ 2624 Graph Automata Player (AOJ-ICPC 550 点)

グラフに行列は付き物!!! 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

AtCoder AGC 001 C - Shorten Diameter (600 点)

ツリーの問題!!!!!!!! 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…

早稲田大学プログラミングコンテスト WUPC 2019 F - RPG

フロー大好き!!!!!!!! 問題へのリンク 問題概要 頂点 辺の DAG が与えられる。頂点 からスタートして頂点 へと向かいたい。すべての頂点 に対し、 から へと向かうパスと、 から へと向かうパスが存在することが保証されている。 頂点のうちいくつか…

AOJ 3058 Ghost (RUPC 2019 day2-H)

燃やして埋めます。後日ちゃんと詳しくまとめて解説書こうと思う。取り急ぎ。。。 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列は 'L' と 'R' で構成されている。文字列の "恐怖度" を以下のように定義する。 個の index ペア ui, vi (ui < …

AOJ 2903 Board (AUPC 2018 day1-H)

燃やす埋めるを本気で整理する!!! すごく面白い問題だった!!! 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... .......... は下のよ…