533.1

チャレンジ祭りをやりたかったそうです。

250

整数配列が与えられる。ある要素を除去すると、その両隣の要素の積の分だけ得点がもらえるとき、最高得点を答えよ、という問題。

DPやるだけ。

500

見てない。

1000

三種類の文字を使ってN個の文字列を作りたい。ただしどの文字列も他の文字列の接頭辞になっていてはいけない。このとき、文字列の使用頻度と文字の重みコストから、全体のコストを最小化するような文字列群は何通り作れるか答えよ、という問題。

文字列の重みコストと同じコストの文字列の数を覚えておく。使用頻度の高いものから順にコスト最小のものを割り当てていく。ある文字列を割り当てない場合、それの後ろに三種類の文字を付けたものを新たに割り当て可能な文字列にできる、という性質を使って探索していく。全体としてのコストはさほど大きくならないので、適当に枝をかれば終わる...。