290.1

250

デジタル時計の時間を合わせることを考える。H時M分から(H+1)%24時(M+1)%60分になるボタンとH時(M+1)%60分になるボタンがあるとき、最小のボタン使用回数を答えよ、という問題。

まず時を合わせてから分を合わせるだけ。メモ付きBFSを書いてしまったが、検証する時間入れると5点くらいしか違わない気がする。

500

同じ速度で動くN匹のナメクジを同時にKメートル移動させたい。一度に一匹だけ持って移動することができるとして、最短で実現するのにかかる時間を求めよ、という問題。ナメクジは常に目的地に向かって移動し続ける。

結局全部同じ量だけ持って移動させないといけない(これは問題文に書いてある)ので、持って移動させる距離を決めてやれば良い。また、すぐに次のを捕まえに行く方が良い。N回運ぶ必要がありN-1回迎えに行く必要があるが、ナメクジは1回運ばれているので、N-1回運んでいる時間とN-1回迎えに行っている時間だけ自分で進む。これは持ち運び移動距離から算出可能なので、バイナリサーチでちょうど一斉にゴールする持ち運び距離を求めてやれば良い。後は達成時間に換算するだけ。

1100

あるものを買う時に、別のものを一緒に買う必要のあるものがあるとする。このとき物を買う個数として可能な数を答えよ、という問題。

取り敢えず依存関係をlongか何かに埋め込んでやると、単純な木(実際には森)になるように問題が設計されている。各木について、実現可能な購入数を計算してやれば良さそう。それは再帰的にできるはず。後でやる。