Palindromic DNA (UVa Live Archive Europe Southwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2959

問題

AGTCからなるn文字の文字列Sがある。各文字は一文字だけ前後(AをGとかCに)に変更ができるが、隣接した物を同時に変更する事は出来ない。SのT個のseubsequenceを全て回文にできるか？
1<=n<=10,000
1<=T<=6,000

解法

subsequenceが回文になるという制約は回文上の対応する文字が同じ文字でなければならないという制約になり、T個のsubsequenceを組み合わせると同じ文字にならなければならない位置のグループが出来る。このグループに全ての文字が含まれている場合はNOになる。他の場合はどの文字に合わせるかは2通りしか無いので、結局2SATになり解くことができる。