はまやんはまやんはまやん

hamayanhamayan's blog

Folia [NOMURA Programming Competition 2020 C]

https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c

解説

https://atcoder.jp/contests/nomura2020/submissions/13927176

貪欲法で解く。
この方針で解けそうと思えるのは経験かもしれない。
解法が分かれば一瞬なんだけど、この解法と心中できるかというと怪しい。
貪欲法は証明してからが本番という意見もあるが、自分はそこまでの頭はないので、証明より心中をとりがちだ。
まあ、どちらにしろ実験するのがいい。

さて、どのような貪欲方針を取るかであるが、まずは最大値というより、作ることを優先して考えてみる。
基本的には残せる頂点は残す方が、後々葉を作りやすくなる。
なので、基本的な方針としては、根から二分木をできるだけ多く作っていき、それぞれの深さで葉が必要になったら、
必要な分だけ葉を作って、残った頂点は全部二分木を作って増やしていく。
このようにやっていけば、各層について使える頂点の数は最大数になるので、
これで葉が足りなくなったら作ることはできない。

この方針で実験してみると、ただ増やすだけではダメであることが分かる。
例えば、深さが4であるときに増やしまくると深さ4で頂点が16頂点ができてしまうが、
その層で葉が3つしか必要なかった場合はどうしよう。
その層で調整しようとすると、1つ前の層では8頂点で来てしまっているので、8個以下にすることはできない。
それ以上の層も削除する必要がある。
これを実際にやってみると、1層目は2頂点、2層目は3頂点、3層目は3頂点、4頂点は3つの葉となる。
さて、方針をはっきり言うと、次の頂点に行くときに頂点は2倍になるが、それ以降で作られる葉の数を越えるときは、
削除することになるということだ。

さあ、実装量も割と軽い方針にも見えるので、これでよさそう。
これが大事で、貪欲解は「実装が軽い方針」は一般にいい方針に見える。
これは経験則なので、怪しいけどね。

解法としては、頂点を2倍する、その層で必要な葉の分だけ引いて削除する、それ以降で作る葉を越えてるなら、
いらない分を削除する。
これを各層について行って、頂点数を数えると答え。
まあ、こうすると直感的にも最大値も達成できる。

N=0のときがたぶんコーナーケース。
一応分けている。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
ll solve() {
    if (N == 0) {
        if (A[0] == 1) return 1;
        else return -1;
    }

    if (A[0] != 0) return -1;

    ll tot = 0;
    rep(i, 0, N + 1) tot += A[i];

    ll cur = 1;
    ll ans = 1;
    rep(i, 1, N + 1) {
        cur *= 2;

        if (cur < A[i]) return -1;

        ans += min(cur, tot);
        cur = min(cur, tot) - A[i];
        tot -= A[i];
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N + 1) cin >> A[i];
    cout << solve() << endl;
}