baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ atcoder.jp 解説をみてピンと来なかったところを補足する形の自分用のメモです。 まず、K個を足して平均に置き換えるという操作は分かりにくいので 上のように操作をK分木で表す事にする そして、1の頂点の深さをa1....am 0の頂点の深さをb1.....bnとする すると最終的な値をxとした時に それぞれの要素についての最終的な寄与を考えると x = k^(-a1) + ... k^(-am)である事が分かる また、ここで実はすべての葉が1の場合はxが必ず1になる事が分かる。 なぜならその場合、下のようにk個を取った平均が常に1になりつづけるからである よって以下の等式が得られ 1 =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2021%2F12%2F11%2F000155" title="AtCoder Grand Contest 009 E - Eternal Average - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/baitop/20211210/20211210233005.png Hatena Blog https://hatena.blog 2021-12-11 00:01:55 rich https://baitop.hatenadiary.jp/entry/2021/12/11/000155 1.0 100%