269.1

簡単なDPが書けなかった...。

250

?は任意一文字を意味し、*は0文字以上の任意の文字列を意味する。このとき、ある文字列と等価な最短文字列のうち、辞書順で先頭のものを答えよ、という問題。

?*は*?と等価なので置き換え、**は*と等価なので置き換える、というのを延々とやるだけ。

500

破壊したいオブジェクトと爆弾が配置されている状況で、任意の爆弾に点火することで、すべての破壊したいオブジェクトを破壊できるようにするために必要な爆弾の最小威力を答えよ、という問題。

威力でバイナリサーチ。爆弾は誘爆するので、どの爆弾を最初に選んでも、目的物がちゃんと破壊されるかどうかのルーチンを書くだけ。特定の一個だと思ってやったら間違えた。

1000

円形に並べられた3*N個のものを、ある一つを取ると、両隣が取れなくなるという条件で選択するとき、得られる最大コストを答えよ、という問題。

結局あるものを取ると両隣が取れなくなるだけなので、順番を工夫すれば、一個おきであれば任意に選択できる。なので隣接するものを取らないようにN個選択して、コストを最大化するDPをやるだけ。先頭のを取ったときに、最後のを取れない、というのをうまいこと一つのDPにまとめることができなかった。普通に二回回せばいいんだけれども...。