Educational Codeforces Round 67 (Rated for Div. 2)
ECR67のバチャ
A Stickers and Toys
問題：意味不明。サンプルを読んだ感じ、N-SとN-Tのmax+1を出力すれば良さそう
B Letters Shop
問題：文字列Sの先頭何文字かを使って文字列Tを作りたい。最低何文字取ればよいか。
考察：
結構制約厳しめなので、効率よく探索しないと間に合いません。
文字列Tにそれぞれのアルファベットが何回出るか数えます。この各文字の文字数以上になるような、Sで一番前のindexがわかればよいです。
これはあらかじめSを前から見て各文字の各回数で記録しておきましょう。
空間計算量は26|S|なのでそこまで大きくありません。
したがってO(|S| + 26m + sum(|T|))で解くことができました。
C Vasya And Array
問題：N個の整数列Aを構築したい。Q個のクエリが与えられ、全てを満たさなければならない。
クエリ0：範囲l、rを単調非減少ではなくする
クエリ1：範囲l、rを単調非減少にする
考察：
各クエリについてかなり自由に組めそうです。
クエリ1から処理します。クエリ1で指定された範囲の隣合う要素は単調非減少にします。boolかなにかで記録しましょう
次にクエリ0の各範囲を全て見て、全てが上でつけた単調非減少になっていたら構築できません。
この雑な処理で間に合う当たりが優しいですね。もっと制約大きいと、重なっているクエリをマージするなどの工夫が必要そうです。
最後に具体的な数値ですが、単調非減少であるところは10^9、そうでなければ1つ前-1などで良いです。
正直なんでもOKです。(全部クエリ0のとき全部1の単調非減少になって１ペナ食らった顔)
D Subarray Sorting
無限にREした
問題：長さNの整数列A,Bが与えられる。自由にクエリを与えてAをBに変更したい
クエリ：範囲ｌ、ｒをソートする
変更は可能か？
考察：
Aのある要素aiをBの要素bjと一致するindexに移動させます。
aiより左にあって、aiと入れ替えられないものはaiより真に小さいものです
あとの考察から、等しいものも含むことになります
上でいう、小さい要素が、bjより左にある全要素の個数を上回る場合、どうやっても達成できません。
厳密な証明は省きますが、右側に動かせない要素があるとき、左側に動かせない要素が必ず存在するのでこのチェックで十分です。
また、要素の各種類の個数も一致している必要があります。そして同じ要素はAで左側からk番目のものを、Bの左側からk番目のものとマッチさせれば良いです。
このことから、上でいう、真に小さいものと等しいものを考えることになります
実装：
vector<int,queue<int>> idx;
を使い、各数字ごとにindexを保存
左側から見て、数字ごとにセグ木でまとめて小さいものをlogNで数えました。
idxに追加するときエラーはいたんですけど、これほんとにai<=n,bi<=n満たしてる？
なんだか納得いかない。
E Tree Painting
問題：各頂点が白で塗られたN頂点の木が与えられる。はじめに任意の頂点を選び黒で塗る。全て黒になるまで、黒に隣接する白の頂点を黒で塗る。
各塗る操作で、塗る前にその頂点と白の頂点だけで連結な頂点の個数分、スコアを獲得する。最大スコアはいくつか
考察：
木の問題なので根付き木で考えます。
シミュレーションしてみましょう
ある頂点から始めると、その子ノードは、各頂点子ノード分しかスコアが得られません。
親を辿ると、辿ってきた子ノード以外でも上の事が言えます
したがって、辿るパスが長くなったほうが良いです。そのため葉から始めることが最適になります。
あとでわかったけど、この考察抜きでも同じ計算量で答えが求まるのであまり関係ないです。
基準スコアとして、全ノードで子ノードを足したものとしましょう。
はじめの頂点を選んだときどのくらい得をするかを考えます。
親までのパスでN-child[vの1つ前(開始地点ならこの項はない)]を得ます。また本来得るはずだった基準スコアに含まれるchild[v]をもう一回引きます
vの1つ前となるところが実装しづらいです。ちゃんと解析するとscore[root]=0で、そのほかの頂点ではn-child[v]*2になります。
これを根からdfsして親+自分のコストとしていけばO(N)で求まります
全体で最大のスコアになる点を選び、計算すれば求まります
反省点：
親の顔より見たオーバーフロー
2回目のdfsでスコアを前計算するところの高速化が必須でした。こちらは仕方ないミスかなって感じです。
ただ考察含めて結構スラスラできたので良かったと思います。このくらいの難易度なら素早く通すことを目標にしたいですね。
F Expected Square Beauty
問題：N個の整数列Xが確率で与えられる。各要素xiは[li,ri]から同様に確からしく整数が選ばれる。この整数列Xで、B(x)を隣接する要素をマージしたときの長さとする。B(x)^2の期待値を求めよ
考察：
最後に二乗するので、途中でいくつになったかを持たないとダメでした
DP[i][j]：i個目まで見て、j個になる場合の数とかでしょうか。ただこれO(N^2)だし、前の要素を考慮できないしで欠陥です。
DPをすると結構計算量大きくなるのでもっと考察伸ばさないとダメですね。解説読んで勉強します
解説：
B(x)=ΣLi(x)
Li(x)=iとi+1が違うかどうか。
B(x)^2=ΣLi(x)*ΣLi(x)
E(B(x)^2)=ΣΣLi(x)*Lj(x)
こうなるらしいです。冷静に考えれば当然ですが、この先が見えない中でこの変形はかなり厳しく見えました。
i==j：Li(x)=Lj(x)=0，1より同時確率はLi(x)
abs(i-j)>1：離れているので独立
abs(i-j)==1：3つの要素でのホウジョを考えればわかる。左の2つが一致は0、右の2つ一致も0、3つ一致をダブルカウントするので足す感じです。
以上から、全体の確率の和を事前計算することでO(1)Σを1つ外せます
したがってO(N)で解けました。
ポイント：
まず数学パートで式変形がしんどいです。明らかにDPではないので、式変形で計算量を落とすって流れで考察するんですかね。難しい；
独立な場所と、そうでない場所に分けます。ここは慣れれば自然にできそうかなと思いました。統計ちゃんとやらなきゃなあとか思いましたね。
ホウジョは簡単な形なのでそこまで躓かないかなと思いました。全体的に実装が重くて、端のコーナーにも対応しなきゃいけないなどエデュフォの最後らへんはやはり難しいですね。
うーーん、類題をほぼ触ったことないんですけど、このレベルがコンテスト中に自力で通せる気しないなあ。キョウプロってオモシレー
全体の感想
最後の最後でE通すまでは3完+41で454位
E通して4完+216で388位と結構上げることができました。良かったです。
Eはあっさり通すべきかなって感じでしたけど。結果通ったのでそこまで悪くないと思います。
