2019/12/29

Codeforces 1270 B

区間長の条件がある

→条件式をいじって、数列の各要素からindexを引いた配列、足した配列を作って、適当な差が1以上になっていればok

もっとシンプルに、隣接2要素の差が2以上⇔条件を満たすものが存在する より隣接二要素を全探索するだけでよかった(数列の要素を平面にに並べると見えやすそう)

 

 

Codeforces 1270 C

適当に実験をしていたが、いい性質が見つからず無限時間が経過...

冷静になるとxorとxor+sumを追加すればよいとわかる

(xorを追加するとxorは0,sumはxor+sumになり、次にxor+sumを追加するとそれぞれ2(xor+sum),xor+sumになる)

xorを0にして、全ての場合をまとめると楽

 

適当に数を大きくして調整することも考えたが、重そうだったので却下...(ごり押しで通す力が欲しいが、量を積んで重い考察に慣れるしかなさそう)

 

 

ABC149 F

期待値

グラフを書いて実験してみる

葉は穴あきとしてカウントされることはない

→ある頂点を通る辺の本数→部分木の個数が重要

ある頂点の穴あき度の期待値を考える(期待値の線形性より、各頂点について考えてまとめてよい)

その頂点を根とする、各部分木の頂点数をa1,a2,...とすると、穴あき度の期待値は

(1/2) *(1-Σ{(1/2)^(n-1-ai) } +Σ{(ai-1)*(1/2)^(n-1)})となる

(その頂点が白で、少なくとも二つ以上の部分木内に黒頂点がある場合は穴あき度としてカウントされる→1からカウントされない場合の確率を引いている)

 

 

多段階の考察、手掛かりを見つける実験に慣れる