■ [others]JOI本選2013オープンコンテスト 
突然のオープンコンテストでうれしいイベント。
1
交互になってる区間を調べて…とやろうとしたら交互の判定が少し面倒。
全体を最初に010101...とxorとってやると、01が交互になっている区間→同じ数字が並んでいる区間 と言い換えられて考えるのが楽になる。
あとは隣り合った3つ以下の区間で長さの合計が最大のものが答え。
1ってこんな難しいんだっけ
2
いかにもDP。
偶数番目と奇数番目で使う文字が違うのでDP用の配列を2つ用意した。1つでもできるとは思う。
3
時間きつそうなのでC++で。
ただの最短路じゃないかと思ってダイクストラ書いてたら全然通らない。60点しか取れず。
隣接するノードにだけじゃなくて到達可能なノード全部に枝を張ってたのでそれが原因かもしれないが、TLEだけじゃなくてWAもあるので通らない原因はほかにもあるのだろう
4
dp[i][j]:=i文字目まで見たときに、リーチのものがj個ある状態での最大ミニ塔作成個数 でDPした。
N^2で50点。
状態としてリーチのもの（先頭2個まで集めたミニ塔）の個数だけ覚えておけばいいのは、先頭1個だけの作成途中ミニ塔がいくつあるかは単純に「i文字目までのI,Jの数-作成したミニ塔の数*2-リーチの個数」で出せるので考えなくても良いから。
それと、Oが出てきたときにあえて使わないことで状況がよくなることはないから。
5
部分点狙いのO(N^2)に絞って考えた。
ひとまず2つを入れ替えるというのは置いておいて、i番目の数字をj番目に置いたときに交換回数の変化がどうなるかを全部調べる。
これは1つのiについてjを1ずつずらしながら累積和取っていったら計算量O(N)でできるので全体O(N^2)。
あとはこれを使って、位置iと位置jの数字を入れ替えたときの交換回数の変化がO(1)で計算できるので全体でO(N^2)。
30点（Javaで書いたらTLEで20点しか取れなかったのでC++にしたら30点になった）。
合計
100+100+60+50+30=340点
オープン参加中4位/40人くらい
3問目ではまってしまって4・5をあまり考えられなかったのが残念。
こういうお楽しみコンテストのときは、デバッグに時間使うよりも面白そうな問題を考えた方が良いかな…
