364.1

飽きるまでちょこちょこ。

300

気合ソート頑張れ、という問題。

やるだけ。

500

N個のもののうち、一部がActiveな状態である。Activeな状態のものは別のものをActiveな状態にすることができるが、コストがそれぞれ異なる。高々KこのものをActiveにしたいので、最小のコストを求めよ、という問題。

MSTの類かと思ったが、明らかにNが小さいのでただのDPの模様。Activeな集合を状態にして、任意に一つ追加していく。ダイクストラでもできそうだが、何も考えずにDPする方が安全そう。

1000

N人の人がそれぞれ一つずつものを持っている。最初の人から順番にswapを高々一回ずつ行っていって、目的の終了状態にしたい。swapはできるだけ番号の若い人とやることにするとき、各人の作業を順に答えよ、という問題。

基本的には自分の欲しいものを持っている人とswapしたいが、その相手が欲しいものを持っている人とswapしておけば、その相手がswapする相手が自分になるので、目的のものが手に入る。このプロセスを再帰的に解決してやれば良い。このようなグループの中で、自分が一番若い番号だとすると、いつかは誰かがswapしてくれるはずなのでswapは不要で、そうでなければ一番若い番号の人とswapしておけば良い。