366.1

新しいキーボード効果。(簡単セット)

250

音量を指定された量だけ増やすか減らすかできる状況で、上限値を越えることなく、最後の状態の音量をできるだけ大きくしたい。当然負の音量は実現できない。最終状態の最大音量を求めよ、という問題。

到達可能な音量をメモしておいて、次の状態に進むだけ。

500

機能の異なるものがいくつかあり、各機能についてできるかできないかが与えられる。できるだけ多くの機能を実現しつつ、必要最小限のものにとどめたい。これを実現する集合のうち、辞書順で最初のものを答えよ、という問題。

集合のサイズが高々10なので、1024通り試せば良い。実現できる機能、それを達成する集合の辞書順でソートしてやる。

1000

開始位置から目的地まで指定されたステップ数で移動するが、入ることによりペナルティの生じるマスと、入った直後に移動するとペナルティの生じるマスがある。目的に途中で寄ってはいけないことと、直前に入ったマスには戻れないということを踏まえつつ、指定されたステップ数で目的地に到達するまでの最小ペナルティを答えよ、という問題。

ステップ数が小さいので、あるステップ数で各状態について最小コストをメモしておいて、それを探索するだけ。