グラフの直径と半径

　九月からブログ再開すると言っていたのに、いつのまにか10月になってしまった。なんでもいいから書こう。（とはいえ、こんなので良いのかな……）

東京大学プログラミングコンテスト2013　C - 直径

　を解いたが、最初、WAを出してしまった。

　まず、答えを書く（解説pdf通りです）と、

・グラフの直径：出来上がるグラフ上で最も遠い２点間の距離

・グラフの中心： もっとも遠い頂点への距離がもっとも小さい頂点

・グラフの半径：グラフの中心から最も遠い頂点への距離

　としたとき、

・最大値：直径の和+1

・最小値：半径の和+1もしくは、元の直径のうち大きい方

　となる。

　そこまでは分かったのだけど、自分は、半径＝（直径+1）/2（切り捨て）と勘違いした（これは木なら成り立つはず）ためWAを出してしまった。変な先入観を持つのは避けなければ。

　次のようなグラフを考えれば、これは成り立ちませんね。

　このグラフだと直径＝2、半径＝2となる模様。