372.1

250

車が道を譲る規則が与えられるので、特定の車が出てくるのが何番目か答えよという問題。

煩雑な規則を読みとって、サンプルが通れば多分おしまい。

500

ある数字の特定の桁を書き換えて、11の倍数にする。このとき書き換えた量だけコストが発生し、使えるコストが与えられている時に、11の倍数になった時の残りコストを得点とする。作成できる全ての11の倍数に対するコストの合計を求めよという問題。

11で割った余りと、消化した桁数、残りコストの三つでDPをすればおしまい。

1000

車がある区間に入った時間と出た時間が与えられ、スピード違反している場合には速度に応じた罰金を回収する。どの車が入った時間かが不明の場合に、回収される罰金の最小額と最大額を求めよという問題。

罰金に応じてグラフを作成し、最小費用流。罰金が多いほど良いとするか、その逆かの二通り計算すればおしまい。単純にダイクストラを何回かやれば終わるけれども。

ダイクストラだと枝がコスト負になりうるのでダメ。二部グラフマッチングか何かだろうなぁ。