heno239 https://blog.hatena.ne.jp/heno239/ heno239’s blog https://heno239.hatenablog.com/ まえがき 解説PDFが閲覧できなくなっていたのと、ネットに自分の解法が落ちてなさそうだったので書きました。 問題概要 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2597 解法 とりあえずグラフを作る。4色定理があるので答えは4以下。 答えが1かどうか→グラフに辺があるかどうか 答えが2かどうか→グラフが二部グラフかどうか なので、答えが3かどうかを調べる。 まず、色1,2,3があったときに、色3となる頂点が全て決まっている場合、これは残りの頂点を2色で塗る問題に帰着される。 そこで問題となるのが色3となる頂点の決め方に2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fheno239.hatenablog.com%2Fentry%2F2021%2F12%2F29%2F002854" title="AOJ 2597 Color the Map Extreme - heno239’s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-12-29 00:28:54 rich https://heno239.hatenablog.com/entry/2021/12/29/002854 1.0 100%