Sorting by Reversals

http://rosalind.info/problems/sort/

前にもだいたい同じ問題が出たので、それの小変更でよい。
ただ、制限時間の5分に近い時間がかかってしまう。たいていの問題は瞬時に解けるのでたぶん速い解法があるはずなのだ。しかし、検索してもなかなか出てこない。そのうちにこれはパンケーキ問題と呼ばれていることに気が付いた。

http://en.wikipedia.org/wiki/Pancake_sorting

この問題に学生時代のビル・ゲイツが取り組んだそうで、論文も残っている。
なぜバイオと関係あるかというと、塩基配列が少ない回数の反転で一致すれば近い配列だとみなせるかららしい(よくわからない)。

さて、先に述べた改変を施して、データをダウンロードして、コードを動かしてみた。おかしい、なかなか終わらない。仕方がないので、アップするはずの出力ファイル名だけ入れて待つ。残り10秒になって終わったので、ボタンを押してサブミット。ギリギリ間に合った。
あとで気づいた。そういえばPyPyを使っていなかった。

今日の帰りにも気が付いた。両側から攻めればたぶん速い。

組んでみたら3秒になった。