SRM417

250

文字列処理。トータルのスコアを更新するときにprefixのスコアを更新するのを忘れて落とされた。

500

与えられた平面図が立方体の展開図かどうか判定しろという問題。立方体の展開図の形は合同なものも含むと11通り(cf:http://www004.upp.so-net.ne.jp/s_honma/spread/spread.htm)しかないなので全通り試す。

1000

平面上にグラフが与えれたときにグラフ上の距離で最も遠い2点の距離を求めよという問題。ただし点はグラフの頂点にあるとは限らない。
今二つのエッジを(A,B)(C,D)とするとAから出発して(A,B)(C,D)を通ってAに戻ってくる方法は

A->D->C->B->A
A->C->D->B->A

の二通りしかなくて、この閉路の短いほうの半分の距離が(A,B)(C,D)上の二点で最も離れている距離になる。これを全エッジ対に対して計算してやればよい。気付かなかった。Opened