AtCoder Beginner Contest 115 - 空母のブログ

AtCoder Beginner Contest 115を解きました。

$D=25$ なら'Christmas'と出力し、24以下なら足りない分だけ'Eve'を追加で出力する。

if文で全パターンやる。

今回の問題の場合なら最初に'Christmas'と出力してfor文を使って $D \leq 24$ の間'Eve'を出力する方法もある。

品物をN個買ったときに、定価が一番高い品物が半額になって残りは定価になるときの支払合計金額。

N個の品物の定価の合計と定価の最大値を求めて合計から最大値の半分を引いたものを出力。

$h_{max}-h_{min}$ の最小値を求める。

配列hをソートしてi=0からi+k-1<nの範囲の全パターンの最小値を出力。

レベル0のバーガーはパティ1枚である。

レベル $L(L \leq 0)$ のバーガーはパン1枚、レベル $L-1$ のバーガー、パティ1枚、レベル $L-1$ のバーガー、パン1枚を積み重ねたものである。

レベル $N$ のバーガーを下から $X$ 層食べたときのパティを食べる枚数を求める。

単純な解き方の場合、レベル $N$ のバーガーを作り下からパティの数を数え上げる方法が考えられるが、 $N$ に対する層の数は $2^N$ なのでTLEになってしまう。

そこで、以下の2点に注目する。

・レベル1以上のバーガーの層 $A_N$ は1つ下のレベルのバーガーの2倍に3を加算した数

・パティの数 $B_N$ は1つ下のレベルのバーガーの2倍に1を加算した数

この2つの情報を使って再帰で解く。

再帰関数はバーガーのレベル $N$ と食べる層の数 $X$ を受け取り食べたパティの数を返す。

受け取った値から3つの状態に分けることができる。

$K \leq A_{N-1}+1$ ：半分も食べない return dfs(N-1,X-1)

$K = A_{N-1}+2$ ：半分まで食べる return $B_{N-1}$ +1

$K \geq A_{N-1}+3$ ：半分よりも多く食べる return $B_{N-1}$ +1+dfs(N-1,X-( $A_{N-1}$ +2))

これをレベル0になるかKが1以下になるまで続け、レベル0のときにXが1以上なら1を返し、それよりも前のレベルででXが1以下になったら0を返すと解ける。