A. Construct an Array
$1, 3, 5, \ldots$ と並べればよいです．
B. Another Sorting Problem
難しい．
$A_{i}>A_{i+1}$ となる場所に注目します．$i$ は加算なし，$i+1$ は加算ありと確定します．加算する値の下限も手に入ります．
確定したポイントの間を考えます．
- $A[i]$：加算なし
- $A[i+1]$：加算あり
- $A[j]$：加算なし
- $A[j+1]$：加算あり
$A[i+1], A[i+2], \ldots, A[j]$ のどこかで「加算あり」から「加算なし」に切り替わる必要があります．この範囲での $A[p+1]-A[p]$ の max を $d$ とすれば，$k\leq d$ が必要です．
こうして作った $k$ の上下限が矛盾しないというのが必要条件です．これは十分条件にもなっていて，確定ポイントの間を一回だけ「加算あり」から「加算なし」に切り替える戦略でうまくいきます．
C. Chipmunk Theo and Equality
それぞれの値から到達可能な値の種類数が少ないです．シミュレーションすれば各到達可能な値に対して操作回数最小値も簡単に分かります．
すべての値から到達可能な値も全列挙できますし，そこに向かうためのすべての数からのコストも計算できます．
D. Maximum Prefix Sums
$c$ が減ることがあれば矛盾です．
$c$ が増える位置では，$a$ の prefix sum が確定しています．これを確定ポイントとして，確定ポイントの間の埋め方を考えます．
この間では，
- いくつかの $a_i$ は既知，いくつかの $a_i$ は未知
- 目標とする $a_i$ の総和が決まっている
- prefix sum がいくつを超えてはいけないという制約がある
という感じの条件を考慮することになります．未知の項が $1$ つ以上あるときについて，総和だけが決まっているという自由度がありますが，その中でも prefix sum をなるべく小さくしてしまいたいので，貪欲な選択が可能です．未知の項のうち末尾以外の部分については十分小さな値（$-\infty$ のようなもの）で埋めて，総和制約を満たすように残りを埋めればよいです．
$-\infty$ のようなものといっても，$|a_i|\leq 10 ^ {18}$ という条件があるので，末尾の未知の項に入れる値が巨大になりすぎないように考える必要はあります．
E. Graph Cutting
いくら注釈が後ろにあるとはいっても「how many different such subgraphs he can cut out」は誤読しない方が不自然な気が？読解注意です．
木 DP です．コストは選んだ点から LCA までのパスの和集合です．subtree 内で選んだ点の個数，コストの組を状態として数え上げをすればよいです．
いわゆる $2$ 乗の木 dp の形にできて，計算量 $O(n^2)$ になります．
F. Quadratic Jumps
任意の正整数は $4$ つ以下の平方数の和で書けるため，コストは $4$ 以下です．
「$1$ ですか？」「$2$ ですか？」「$3$ ですか？」
を判定できればよいです．$1$ かどうかの判定は簡単です．
$3$ かどうかの判定は，最初の $1$ 歩を全探索します．結局，「$2$ ですか？」が $O(1)$ でできればクエリ処理は計算量 $O(q\sqrt{n})$ が達成できます．
「$2$ ですか？」を $O(1)$ で解きます．$d$ ごとに「$0\to d$ と行くときに，区間 $[0,d]$ からはみ出る値の最小値」を前計算できればよいです．
「$d=x^2+y^2$ と書けるか？」「$d=x^2-y^2$ と書いたときの $y^2$ の最小値は？」などを前計算できればよいです．後者は $d=(x-y)(x+y)$ という因数分解を利用すれば $O(n\log n)$ 時間になります．
