ishikado https://blog.hatena.ne.jp/ishikado/ ishikadoのアルゴリズム勉強録 https://ishikado.hatenadiary.org/ 辺を共有する図形同士をノードとしてくっつけ、グラフを作る。 塗り方は、国の名前が11あったとしても67万以下程度になるらしい(http://apps.topcoder.com/wiki/display/tc/SRM+496のdiv2hard参照)ので、すべての塗り方を試し、妥当かどうかをたしかめる。 確かめるところで最悪の場合（グラフがクリークになっている）O(4.0*10^4)かかってるので、全体でO(2.4*10^9)程度になり、間に合うか微妙かなーと思ったが、図形の配置的にクリークになることは考えにくいと思い、提出してみたら2.0s程度でACした。 チェックするところはもっとうまくやれば… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fishikado.hatenadiary.org%2Fentry%2F20111106%2F1320598481" title="aoj 1254 - ishikadoのアルゴリズム勉強録" 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 2011-11-06 01:54:41 rich https://ishikado.hatenadiary.org/entry/20111106/1320598481 1.0 100%