A - Strange Subset Sum

ヒント 1

$|A|=\left\lfloor\frac{N}{2}\right\rfloor$ の制約から、$1$ 以上 $N-1$ 以下の整数のうちおよそ半分が $A$ に含まれることがわかります。 これから何が言えるか考えてみましょう。

ヒント 2

たとえばランダムにケースを生成した場合、ほとんどのケースで答えは $2$ になります。それはなぜでしょうか？

ヒント 3

$i=1,2,\dots,\left\lfloor\frac{N-1}{2}\right\rfloor$ について、$i$ が $A$ に含まれるかどうかを聞きます。その結果を使って残りおよそ $\frac{N}{4}$ 回で $2$ かどうかを判定する方法を考えてみましょう。

ヒント 4

ヒント 3 で $2$ ではないと判定された場合、$A$ の要素はすべて特定されているはずです。

ヒント 5

実は、答えとしてあり得る数はそれほど多くありません。

B - Count of Euclid Function Call

ヒント 1

ユークリッドの互除法の手順を逆から考えてみましょう。

ヒント 2

呼び出される $f$ の引数は $an+bm,cn+dm$ と表されます。ユークリッドの互除法を逆にたどるのは、$(a,b,c,d)$ に対してどのような操作を行うことに対応しているでしょうか？

ヒント 3

$\begin{pmatrix} a & b\\ c & d \end{pmatrix}$ に対する操作だと思うと、操作の前後で不変な量は何でしょうか？ それをもとに、$a,b,c,d$ の条件を考えてみましょう。

ヒント 4

$c,d$ を固定したときに、ヒント 3 でわかった条件を満たすような $a,b$ について考えてみましょう。

ヒント 5

$a,b,c,d$ の条件やそれを満たす $a,b$ について、コーナーケースがないかに注意してください。

C - Equal Degree Deletion

ヒント 1

特別な木の条件に付いて考えてみましょう。

ヒント 2

消されるタイミングでの両端点の次数をその辺に書き込んでみましょう。

ヒント 3

各頂点から出る辺をまとめてみたときに、書き込まれた次数についてどのような条件があるでしょうか。

ヒント 4

$d$ が書き込まれるような木を作るためには $2^d$ 個以上の頂点が必要です。

ヒント 5

辺に書き込まれる次数の最大値は $O(\log N)$ です。

ヒント 6

根を適当に決め、上に上がってくる辺に書きこまれている次数をキーにしてボトムアップに dp をします。どうすれば実行時間に間に合わせることができるでしょうか？

ヒント 7

書き込まれる次数をある値にするためにはそれに応じた頂点数が必要なため、それらをまとめて上から評価することができます。 それを活かす工夫によって dp の計算を高速化することができます。

D - Zigzag Code for Cubic Functions

ヒント 1

$|S|$ に関する制約はいったん無視して考えてみましょう。 また、$f$ が $1,2$ 次関数の場合も考えてみましょう。

ヒント 2

$f$ が $1$ 次関数の場合は、$g(S+\mathtt{-+})=g(S)+1$ が成り立ちます。 $f$ が $2$ 次関数の場合は、$g(S+\mathtt{+--+})=g(S)+4$ が成り立ちます。 これらを $3$ 次関数に拡張してみるとどうなるでしょうか？

ヒント 3

$i=0,1,\dots,47$ について $i$ が生成可能かを判定する方法を考えてみましょう。

ヒント 4

$|S|$ の制約があるため、$g(S+T)=g(S)+48n$ となる短い $T$ をそれなりに大きい $n$ について作る必要があります。 ヒント 2 で考えた文字列に工夫を加えてみましょう。

ヒント 5

$\mathtt{+--+-++-}$ の各文字を $k$ 回ずつ繰り返して連結させた文字列を後ろに連結させるとどうなるでしょうか？