Round 3

なんか運よく通過してしまったｗ
一人旅とかやばい…英語勉強しないと…

A

全て連結という条件から状態数がとっても減るのでてきとーに幅優先探索するだけ

B

smallは全組計算するだけ
largeもいっぱい提出があったのでずっと考えてたけど、さっぱり分からなかったorz

C

グラフを作ると、平面かつ全ての内面が三角形であることが簡単に証明できる
平面グラフなので、３彩色できるか判定出来ればよくて、三角形性を使うと、線形時間で解ける
まず、ひとつ三角形を彩色して、それと辺を共有する三角形の残りの頂点は色が一意に決まり、共有しない三角形の頂点は、どんな色で塗っても、もう合流しないからどうでもいい
ちなみに組むのめんどかったから彩色ライブラリをコピペったがちゃんと通ったｗ(追記: これじゃだめなケースがあったorz)
ところでこのグラフなんていうんだろう…

D

あまり解かれていなかったのでほとんど考えてない
smallくらいは解くべきだったorz

合計48pointの12位