A問題

条件分岐を使って解く. または, 25 - $n$ 日は $n$ 回 Eve がつけば良いので, 演算子 * を使う.

計算量としては $O(\, 1 \,)$

B問題

1つの商品しか割引してもらえないので, 最大のものを割引してもらえば良い.

したがって, 偶数ということを加味して最大値と総和を計算すれば解ける.

計算量としては $O(\, N \,)$

$n$ 個からなる集合から $k$ 個のもの(部分集合)を取ってくる時の「最大値と最小値の差」の最小値を求める問題.

「最大値と最小値の差」を求めるのには, $n$ 個をソートすると簡単に求められる. そこから, 直ちに最小値は求められる.

計算量としては, $O(\,NlogN\,)$

レベル $N$ バーガー自体がレベル $N-1$ にバーガーによって定義されているので, 漸化式で解く,すなわち, 再帰をすれば良い.

$a_n :=$ { レベル $n$ のバーガーのサイズ }, $b_n :=$ { レベル $n$ のバーガーに含まれるパティの数 }

とすれば, 簡単な漸化式を解くことで, $a_n = 2^{n + 2} - 3$ , および $b_n = 2^n - 1$ が得られる. ( これはビット演算で簡単に計算可能 )

これから, 簡単な再帰関数を書けば良い. DP でメモ化する必要も, 末尾再帰にしてループにする必要もない.

なお, 自分は再帰の止める部分で 2 WA しました.

計算量は $O(\, N \,)$ ?

438位パフォーマンス 1322でした

やっぱり, まずはコードを書くスピードが遅いという点.

今回のミスに限って言えば, 32bit に収まらないということを 64bit に収まらないと勘違いして C++ のコードを一回 Python に直したことも時間のロスにつながった.

基本, 64bit で収まるはずの入力がくるはずだし, 競プロは C 系は不利にならないからそんなことはありえないと考えておくべきだった.