477.1

グラフセット。別名ライブラリゲー。

250

海と陸が六角形を一つの単位として配置されている状況で、海岸線の長さを答えよ、という問題。

要は陸と海が接している数を答えよという問題なので、6方向調べる。

500

整数配列が与えられるので、平方数の和が平方数になる互いに素なペアは最大いくつ作れるか答えよ、という問題。

一見すると一般グラフのマッチングのように見えるけれど、互いに素であることと、片方が偶数じゃないと平方数の和が平方数にならないことから、偶奇で二部グラフになるので、二部グラフマッチングをするだけ。後は最大流ライブラリを使いましょう。

1000

ツリー上の都市配置があり、開始点と終了点が指定された同じ点であるように移動したい。すべての辺を少なくとも一度は通るが、高々K回だけコストLで任意の地点へのショートカットができるものとする。このとき最小の移動コストを求めよ、という問題。

全然うまく説明できないけれど、最小費用流...。グラフは開始点と終了点を追加して、開始点からすべての点にコストLの枝を、すべての点から終了点にコスト0の枝を追加して、元のグラフは枝のコストをマイナスにしておく。こうすると、ショートカットを入れるときに、L-(一番コストの大きいパス)がまず除去されて、次にL*2-(一番コストの大きい、辺を共有しない二本のパスの組)が除去されて...という感じになる。最初はすべての辺のコストの2倍からスタートして、コストを減らすように高々K回流せばいいだけ。

実際にそういうショートカットが存在するかどうかは、最初のパスの終了点と次のパスの開始点、そのパスの終了点とさらに次のパスの開始点...、という感じでショートカットを結んでやってうまくいく。(パスが辺を共有しないため。)