661.1

久し振りにしっかりした問題だった。

250

整数Nが与えられるので、N+1からKまでの整数の最小公倍数と1からKまでの整数の最小公倍数が一致する最小のKを答えよ、という問題。

1からNまでの整数のうち各素数で割り切る最大回数を求めて、それが次に出てくる位置を覚えておく。その位置の一番大きいのが答え。

450

N個のノードのあるグラフを考える。色がK色塗ってあって、各ノードは自分よりも番号が若くて色の違うノードに対して枝をはることができるし、はらなくても良い。このとき、可能なグラフは何パターンあるか答えよ、という問題。

良く分かっていないけれども、二色の場合は階乗になるし、三色の場合は奇数のみの階乗になるし、という感じで、一般化すると、色の数-1飛ばしの階乗になる模様。後はmodを取るので、ループするまで頑張る感じ。

多分数学的には有名な何かなんだろうなぁ、とは思います。

1000

一列にノードが並んだグラフが二つ与えられるので、同じ番号のノードをマージする操作を高々K回やってよいので、全二点間の距離の最大値を最小化せよ、という問題。

良く分からないけれど、頑張ればDPみたくできるのだろうか？