TCO 2010 Qualification Round 1

キャンセルになったけれど、メモくらいは残しておいてあげてもいいかなぁ、的な。

250

DNAの断片がいくつか与えられるので、ペアになっているものがないように選ぶことができる最大数を答えよ、という問題。

ある二つがペアになっているならば、それらは他のどれともペアにはなり得ないので、どっちか片方を捨ててやればいいだけ。つまりすべての組み合わせを調べてペアになるものの数だけ引けばいい。

500

文字列の任意の位置の文字を書き換えることで、回文にしたい。書き換えの数を最小にして、できる文字列中の文字の種類を最小にし、さらに辞書順で先頭のものを答えよ、という問題。

文字列長が30文字までなので、回文にするために書き換える場所の候補は高々15組。(この時点で書き換える数を最小にするという条件は解決されている。)各組の中ではどちらかを書き換えるので、全部試しても2^15通り程度。出てくる文字数と文字列の辞書順で適当にソートして最初のものを答えればおしまい。

1000

見てない。