496.1

比較的簡単なセット。

250

縦方向に青色、横方向に赤色の線が引ける。両方の線が交差したら緑色になる。このとき、線を引いた結果の色の分布が与えられるので、少なくとも何本の線を引いたか答えよ、という問題。

縦方向に青か緑の連続成分がいくつあって、横方向に赤か緑の連続成分がいくつあるか、というだけの問題。

500

向きは不明だが等速で移動している物体がN個ある。ある時点での位置と、そこからしばらく経った時点での位置にK個の物体を追加したものが与えられるので、最初のものが移動した位置として可能なものは何通りあるか答えよ、という問題。

その期間に移動した距離は高々N+K通りくらいしかないので、全部試す。もし移動した距離がDだったとすると、移動先として可能な点は高々2通り。移動先の点に来る可能性のある物体は他に高々1個まで。なので、これらをクラスタリングすると、X個の物体がY個の移動先を共有している状態になり、YはX-1以上X+1以下になる。YがX-1の場合、そのような割り当ては無理だし、Xの場合は一通りしかないし、X+1のときは、使わないのが1個なのでX+1通りしかない。後は適当に場合の数を計算するだけ。

950

N地点に対して文字列が割り当てられており、二点間の移動コストはそれぞれの文字列長の二乗から、共通接頭辞の長さの二乗を引いたものとする。このとき、0番目の地点から1番目の地点へのすべての点を通るような移動での最小移動コストを求めよ、という問題。

結局0番目と1番目の地点以外は2回カウントされる。後は、文字列の共通接頭辞の長さの二乗の和ができるだけ多くなるような組み合わせを考えれば良い。文字列の共通接頭辞の関係はかなり強力な制約で、共通接頭辞の長さをLCPで表現するとき、LCP(S,T)>LCP(S,U)がLCP(T,U)=LCP(S,U)の必要十分条件になる(ような気がする)ので、これをまとめるとかなりGreedyに選択して良い。(一番大きい辺を採用したとき、その辺の端点を使うそれよりもコストのいい辺はない。)

なのでMSTでコストが計算できるけれど、0番目の点と1番目の点を結合するのは最後の辺を追加するときに制限する(じゃないと孤立点ができてしまう)ことに注意する必要がある。