328.1

250

N*N*N個のライトが3次元配置されている。初期の点灯配置が与えられるので、各ステップごとに隣接するものが同じ色で点灯するとして、最終的な色の分布を答えよ、という問題。

やるだけ。

500

ツリー上の都市配置が与えられる。指定された都市間の移動ができなくなるように道を切断するときの最小コストを答えよ、という問題。

重みを逆転させてMSTするだけ。指定された都市群は別グループのままにするように注意。

あるいは、都市間の到達可能性が単調減少するように、コストの小さい辺を全部テストしていくだけ。到達可能性はWarshall-Floydで十分。

1000

二次元平面上の格子点上に距離D離してK本の木を植える。木は同一直線状に並ぶ必要がある。何通り可能か答えよ、という問題。

傾きごとに全探索。N^4なので適当に最適化が必要...。