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; }
