TCO 2010 Qualification Round 2

通らないと思ってたら通った。実装系だとまずまず戦えるっぽい。

250

税金が発生するシチュエーションで、転売をして儲けることのできる最高額を答えよ、という問題。

取り敢えず一番安くかって、一番高く売る、というのを利益が出る限り続けるだけ。

500

セルオートマトンで、いくつか状態の分からないマスがある。次のステートのときに、生存しているマスの数の最大値を答えよ、という問題。

状態の分からないセルが複数見えているセルがない、ということから、状態の分からないセルを順番に決めていくことができるので、実装あるのみ。

1000

ある文字列を特定の文字列セットでカバーすることを考える。その際、一番長くカバーできた領域の長さの二乗から、カバーできなかった文字の数を引いたものをスコアとする。最大のスコアを答えよ、という問題。

取り敢えず、左端を決めて、そこからできるだけ連続してカバーさせる。後は残った領域をできる限りたくさんの文字数カバーするようにする。両端からのマス数さえ覚えておけば、再計算しなくても良いのを利用して高速化する。(これいらないかも？)