8VC Vecture Cup 2017 - Elimination Round

E問題のコーナーケースに気づけなかったのが痛い。

（2017/01/16 15:01: どことは言わないけど、E問題の証明が間違ってたので訂正）

http://codeforces.com/contest/755

A. PolandBall and Hypothesis

全探索。

B. PolandBall and Game

共通するワードを先に使った方が有利である。勝敗判定は、実際にこの戦略に従ってゲームをシミュレーションすればいい。

C. PolandBall and Forest

問題設定から木の形が重要でないことが分かるので、全部パス型の木であると考えてもいい。これは若干卑怯な解法。

実はどのような木でも、最も遠い頂点は高々 2 通りしかないことが示せる。これは実際によく使う性質なので知っている人も多いだろう。

D. PolandBall and Polygon

線を引いていったとき、他の線分と交差する度に面がひとつ増える。何回、線分と交差するかを数え上げたい。

線を引いたとき、短い方の弧から出る辺は、かならずもう一方の弧へと繋がっている。

したがって短い方の弧の上にある頂点の次数の総和は、線を引いたときに交差する線分の数と等しい。これがわかれば、BITを用いて O(N log N) で計算できる。

E. PolandBall and White-Red graph

実験により K≧4 が Impossible であることが予想できる。これを示す。

まず直径となるパスを先に作っておく。

このとき直径の両端のどちらかと、パス以外の頂点は破線で結ばれる。実線で結ぶケースもいくつかあるが、直径の両端両方に実線で結ばれることがないのが重要である。

パス上の頂点同士も、ほとんど破線で結ばれる。そうでないと距離が変わってしまう。

以上のことを考えると、たかだか 3 ステップで任意の頂点に行けることが分かる。したがって、直径 4 以上のグラフの補グラフの直径は 3 以下であることが示された。

さて、K=2,3 のときの構築法を考えよう。

K=2 のときは 1→2→3→…→n というパスを作ればいい。

K=3 のときは以下のようなグラフを作ればいい。

上位の人が D で落としていたためか、Eを落とした割に順位は下がらなかった。