Xmas Contest 2015 お疲れ様でした！
ご参加いただいた方、ありがとうございました。
楽しんでいただけていたら幸いです。
とりあえず、各問題の解法の概要を書いていきたいと思います。
A「Accumulation」
乱数生成が一番難しい、という問題。
f(x) = Ax + B
のときに f^T(x) を求めたい。
f(f(x)) = (A*A)x + (AB+B)
みたいな感じで関数合成をバイナリ法で計算していくと f^T(x) が求められる。
B「Broken Christmas Tree」
解法１：「まだ繋がっていない頂点集合」をsetか何かで持ちながらDFSしていく。繋ごうとした時に繋ぐのに失敗する回数がM回で抑えられるので上手くいく。
解法２：悪い辺の次数が最小の頂点に直接繋げられる頂点をぐいぐい繋いで連結成分を縮約すると、頂点数が√M以下になるので、MSTとかをする。実装大変。
C「Colored Tiles」
解法１：ある2行を取りだして（1≦i≦j≦5 の15組）manacherで最長回文を求めておくと、あとは適当に計算できる。
解法２：中心と高さを固定して取れる限り幅を増やしていく、というような愚直なアルゴリズムで求めていく。ただし、Yesと言われた時はunion findでくっつけておき、次からはその情報をもとにYesだと確定する時はクエリを投げないようにする。すると、Yesと言われる回数が高々HW-1回に抑えられる（uniteの回数は高々頂点数-1）。また、Noと言われる回数も中心と高さの組の個数で抑えられる。
D「Destroy the Duplicated Poem」
解法１：KMPをやるんですが、そのままやるとTLEなので、「ここでこの文字がきたときのfailure link」みたいなのを計算していく。「ひとつ下に潜る」という操作に注意。
解法２：KMPをうまく実装すると一回の遷移がlogで抑えられるらしい。というかこれが本来のKMP。詳細はclimpetさんの提出とこれを読んでください。→記事書きました
E「Esolang?」
部分点は線形リストとかで取れます。
満点のベースアイデアは、vectorみたいに「確保していたメモリが足りなくなったら、新たに倍のメモリを確保する」という感じです。
ただし、vectorみたいに新たに確保するたびにデータをコピーしていると、メモリが4Mぐらい必要なので、配列の線形リストみたいな形で実装します。
データ構造は、[サイズ1の配列]→[サイズ2の配列]→[サイズ4の配列]→[サイズ8の配列]...みたいな線形リストになります。
メモリは2M+N*αみたいな感じで、expr回数はO((M+Q) logM)とかです。
exprの回数制限だけで変なコード（例えばa[a[a[a[a[a[...]]]]]]]]とか）が縛れるのが作問側の知見として面白かったです。
F「FILO Sort」
[B+1,A,B]（A<B）という部分列がないことがソートできる条件。こういう組の個数を数えるのは、前計算：BITやる、クエリ：隣接swapしかないのでO(1)でできる。
考察を進めるほど実装が簡単になる問題だった。
G「Good Sequence」
よく考えると、隣接の差の絶対値の和を求めるだけ。
H「Hybrid Testcase」
この枠は他の問題が出来てから作ろうと思っていて、他の問題の準備がある程度終わってから適当にそれっぽい問題を作ってみたら問題になっていた。
まずA=0 かつ X>T としてみると、X+4B=Z, X+C=Z という式になる。B=Z/4, X=Z%4, C=4B, T=1 とすると9以上は全て構成できる。
あとは8以下だが、A問題の性質上 X は8以下しかありえなくて、G問題の性質上 他の値は X+8 以下しかありえない。となると、考えられるケースを全て試すことができる。
