194.1

昨日の続き。

1000

問題を再掲しておく。ある島から別の島へ移動するコストの最小値を求めたい。チケットは同時に3枚までしか持てず、値段は島ごとによって異なる。各チケットは、いくつかの使い方ができて、ある島から別の島への遷移のうちのいずれかに使用できる。

単純に収束するまでテーブルを更新し続けるだけだった。テーブルは島の数とその時に持っているチケットの種類。ある島にチケットが2枚以下の状況でいるならば、その島でチケットを買うことで状態を更新する。ある島にチケットがある状態でいるならば、そのチケットを使って行ける島に、そのチケットを除いた状態にコスト0で遷移できる。

普通に実装しても速度的に問題にならなかったけれど、チケットが3枚までという制約に従って高速化はできるかも知れない。(実際にはチケットの枚数をステートから計算してすぐにスキップしてしまうので、ボトルネックになるかどうかは不明。)

きっともの凄く難しい問題に違いない、と思って昨日は保留したけれど、よくよく考えてみればただのDPだった。実は今までにスキップしてきた問題もそうなのかも知れない。