SRM654

writerをやってました。実質3問でd2は劣化版です

d2 easy:
やるだけ

d2 med:
d1 hardの劣化で、再帰O(N)で解けるのではじめN>=10000とかに設定しようとしていたが,O(N!*ちょい)になった.

d1 easy:
あるsubstringが条件を満たす確率を、適切な前計算をすればO(N^2K)
そこまでしなくても、"場所iの文字がが寄与するぶん"とかを考えて更新するとO(NK)になります.

d2 hard = d1 med:
適当にいじっていたら出来た問題(このset中で一番初めにあった)
はじめはO(QlogN)の予定でした(seg木を8個もつ)
testerの解では8個が配列にまとめられていてうまく処理されていた.
えっと、seg[x][i][j][k]で、ノードxで連結成分がi+1個,j=左と連続しているか,k=右と連続しているか,を持って更新します.
ちなみに問題作成当時はSuccessiveDivisionでした,符号が変わるのでminも持たねば駄目です.さすがにクソすぎるし誤差も闇なので自重しました.

d1 hard:

東大模試にある特別なグラフのトポロジカル順序の数を問う問題が出ていて、そっから着想を得ました。木じゃなくて一般のグラフにしようとしたんですが出来ませんでした.
s1-s2が一直線の棒になっている時を考えると、うめかたは2^n通りあります.
埋め方の条件は、"内側から埋まっている"ということで、つまり区間DPができます.
あとはそれぞれの頂点からsubtreeが生えているので、それぞれのsubtree内での順序(これはOneEntranceの時と同じようにやれば良い)と、区間DPでこれまでに埋めた個数と今埋めようとしてる個数の順番を考えると適切な組み合わせが生えてくるので、それを実装すればよいです.

全体:
はじめてのwriterで、rngさんとかに色々迷惑をかけてしまった.準備が直前すぎるのはまあアレ.
Javaで想定解やDatacheckerを書くんですが、d2 medでJavaにnext_permutationがないことに気づき若干めんどくさかったです.
あとO(QlogN)バージョンのd1medを出そうとしてた時にtester2人が答え一致して自分が合わなくて非常につらかった)
簡単にしてすいません.rating上がった人はおめでとうございます.下がった人はごめん。