強いぜnuさん - カメヲラボ

http://acm.pku.edu.cn/JudgeOnline/problem?id=3671
USACOの問題は全部牛さんネタなので、問題内容は要約しときます。

ランダムに配置された1と2の並びがあって、1と2は互いに反転することができます。1と2を反転させて、最終的には左側に1だけ、右側には2だけが並ぶ状態を作ります。例えば、

2 1 1 1 2 2 1

という数字の並びがあれば、最初と最後を反転させて、

1 1 1 1 2 2 2

のようにすればOKです。数字の並びには、1と2の両方が必ず含まれている必要がないので、すべて1とかすべて2になってもかまいません。このような操作を行う場合に、数字を反転させる回数の最小値を求めてください。上記の例だと、最小値は2ということになりますね。

DPっぽいかんじの問題ですが、statusを見ると上位がかなり小さなコードサイズでした。コードサイズからアルゴリズムを予測すると、1パスで簡単に最小値を求める方法があるのは間違いないはず。

Topが77Bだったので、とりあえず77Bを切るところまで頑張りました。で、75Bまで削ったところでなんか他の人と消費メモリのサイズが全然違うようで、自分だけおかしなことをやってるんじゃないかという気がしたまま昨日は終了しました。すると案の定、nuさんに大差をつけられていました(;´д｀)

普段ならさっさとコードを晒して終わるところではありますが、問題自体が難しくないのと、かなり短く書けるということもあるので、もうちょっとだけコードを貼るのは控えておきます。2・3日したら公開ということで。ウデに自信のある人も無い人も、nuさんの61B目指してレッツトライ！

ちなみにnuさんは、諸事情*1でショートコーディング本には名前が刻まれていませんが、超絶コーダーの一人であります。

*1:単に出版までに連絡が取れなかっただけですが^^;