AtCoder Beginner Contest 115

0WA全完したが、Dでintとlong longを混同して30分食ってしまいPerf1600は行かなかった。

A - Cristmas Eve Eve Eve

問題: A - Christmas Eve Eve Eve
今回は解く速さを重視したので、nで場合分けするif文を並べまくって問題文の通りに実装した。

拙解 (C++): Submission #3738555 - AtCoder Beginner Contest 115

B - Cristmas Eve Eve

問題: B - Christmas Eve Eve
全ての品物の値段が偶数なので、割引額は最も定価の高い品物の値段÷２になる。これを全ての品物の値段の和から引けばいい。
一応数式に起こす*1と、求める支払金額を $S$ 、最大の定価を $p_m$ 円として、
${\displaystyle\begin{eqnarray*} S&=&\left(\sum_{i\neq m} p_i\right) + \frac{p_m}{2}\\ &=&\left(\sum_{i=1}^N p_i\right)-p_m+\frac{p_m}{2}\\ &=&\left(\sum_{i=1}^N p_i\right)-\frac{p_m}{2} \end{eqnarray*}}$
と求められる。

拙解 (C++): Submission #3739682 - AtCoder Beginner Contest 115

C - Cristmas Eve

問題: C - Christmas Eve
選んだK本の木のうち最大のものと最小のものだけわかっていればいいので、木の高さでソート*2して連続したK本の一番前のものと一番後ろのものの差をすべて取れば、最小の候補をすべて列挙できる。この最小値を求めればいいので、計算量が $O(N)$ になって ${N\le 10^5}$ でも解ける。

拙解 (C++): Submission #3741193 - AtCoder Beginner Contest 115

D - Cristmas

問題: D - Christmas
まず、レベル $N$ バーガーの層の数を $v_N$ 、パティの数を $p_N$ として、
$v_0=p_0=1, v_{N+1}=2v_N+3, p_{N+1}=2v_N+1$
とすると、再帰で解ける。
下半分を丸々食べてしまうときはバン１枚とレベル ${N-1}$ バーガーを丸々食べたことになり、中途半端なところはレベル ${N-1}$ として食べる残りの層 $X$ を調整しつつ真ん中に挟む１枚のパティを考慮しつつレベルを下げていく。
計算量は ${O(N)}$ なので、 ${1\le N\le 50}$ には余裕で間に合う。これで解けた！
…と思ったが、再帰関数のlong long型にすべきxをint型にしていたことに気づかずに30分消費した。