A - Unusual-Constraint Knapsack

ヒント 1

普通のナップサック問題に $\sum_{j=1}^{i-1}{w_j}\lt w_i$ という特殊な制約が付いています。これを活かす方針を考えてみましょう。

ヒント 2

$i=N,N-1,\dots,1$ の順に、荷物 $i$ を選ぶかどうかを探索してみましょう。

ヒント 3

（制約からあり得ませんが、）$W \lt w_N$ ならば荷物 $N$ を選ぶことはできません。$w_N \leq W$ のとき、荷物を選ぶ場合と選ばない場合でどうなるかを考えてみましょう。

ヒント 4

選んだ場合、残りの重さは $W-w_N$ となり、荷物 $N-1$ を選ぶかどうかを探索することになります。選ばない場合はどうなるでしょうか？

ヒント 5

荷物 $N$ を選ばないならば、制約よりそれ以外の荷物をすべて選ぶことができ、探索をここで打ち切ることができます。この性質を使って計算量について考えてみましょう。

B - Valid Arrays by K-Divisible Swaps

ヒント 1

いろんなKに対して、入れ替えることができるような $\text{mod }K$での $2$ 数のペアを書き出してみましょう。

ヒント 2

操作の前後で、各要素は $\text{mod }K$ で $1$ 倍か $-1$ 倍されることがわかります。

ヒント 3

最初の時点で $A_i \not\equiv \pm A_{i+1} \pmod K$ ならば、$A_i$ と $A_{i+1}$ を入れ替える操作が行われることはありません。よって、このような場所で数列を区切って場合の数を求めることができればそれらを掛け合わせればよいです。

ヒント 4

$A_i \equiv -A_i \pmod K$ かどうかで場合分けします。それぞれの場合について、どのような条件を満たせば並び替えることができるかを考えてみましょう。

ヒント 5

$A_i \equiv -A_i \pmod K$ ならば、区切られた数列内の要素は自由に並び替えることができます。
$A_i \not\equiv -A_i \pmod K$ ならば、$\text{mod }K$ で同じ値同士は入れ替えることができないため、それらの順序は不変です。

C - Whole Product of Pairwise Distances

ヒント 1

何かで割った余りを求める問題では、$998244353$ や $10^9+7$ といった素数が法に使われることが多いですが、今回は $N$ です。この違いを考えてみましょう。

ヒント 2

$A_1,A_2,\dots,A_N$ の中に $N$ で割った余りが同じ数のペアがあればどうなるでしょうか？

ヒント 3

$N$ を法として $0,1,2,\dots,N-1$ がちょうど一つずつ含まれる場合が解ければよいです（そうでなければ答えは $0$ です）。 元の式には絶対値がついているため、$A_i$ をいきなり $N$ で割ってしまうと答えが変わってしまいます。どうすればいいでしょうか？

ヒント 4

$A$ をソートして、$\prod_{1 \leq i \lt j \leq N}{(A_j-A_i)}$ を求めると思えば、$A$ の各要素を $\text{mod }N$ で考えても答えは変わりません。 最も単純なケースとして $A_i=i-1\;(i=1,2,\dots,N)$ がありますが、この場合、答えはどのように求められるでしょうか？

ヒント 5

$A$ が $(0,1,2,\dots,N-1)$ の順列のとき、$\prod_{1 \leq i \lt j \leq N}{(A_j-A_i)}$ はどうなるでしょうか？ ヒント 4 の単純なケースとの違いを考えてみましょう。

D - Xpectation of Cards in Hand with Laboratory

ヒント 1

これまでに引いたドローカードと普通カードの枚数を $a,b$ 枚としたときに、操作が終了する条件を数式で表してみましょう。

ヒント 2

ドローカードを→、普通のカードを↑で置き換えたグリッド上の経路を考えてみましょう

ヒント 3

経路に言い換えて考えます。操作が終了するときにいる可能性のある頂点の個数は $O(A+B)$ です。

ヒント 4

各頂点について、そこで終了する条件を考えてみましょう。

ヒント 5

操作が終了したときに山札が残っている場合とそうでない場合で条件が少し異なります。

E - Yin-Yang Two Bits Insertion

ヒント 1

数列を、隣接する要素の差分 XOR で考えると、操作はどのような変換に対応しているでしょう？

ヒント 2

$0$ は $101$ に、 $1$ は $111$ に変換されます。 元の数列と変換後の数列はいずれも先頭と末尾の要素は不変ですが、それ以外にどんな不変量があるか考えてみましょう。

ヒント 3

差分 XOR 数列において、$0$ の個数は不変です。 そこで、$0$ で区切って各区間に並んでいる $1$ の個数を並べた数列で言い換えてみます。 操作はどのような変換に対応しているでしょうか。

ヒント 4

• 隣接する $2$ 項に $1$ を足す
• $1$ 以上の項に $2$ を足す

という操作に対応しています。 ほとんどの場合、$1$ つ目の操作 $2$ 回は $2$ つ目の操作で代替できます。

ヒント 5

$1$ つ目の操作を同じ $2$ 項に $3$ 回以上行う場合、$2$ 回を $2$ つ目の操作にしてもいいです。 このことから何が言えるでしょうか？ また、その性質を使えばどのような動的計画法で判定ができるでしょうか？

F - Zonal Score Maximization

ヒント 1

$f(P)$ は全体の総和 $\frac{N(N+1)}{2}$ 以下ですが、$N$ が偶数の場合はこれを達成できます。 では奇数の場合はどうでしょうか？

ヒント 2

$N$ が奇数の場合は、長さが $3$ の数列 $1$ 個と長さが $2$ の数列 $\frac{N-3}{2}$ 個に分割するのが最適なことがわかります。

ヒント 3

$N$ が奇数の場合、$N-1$ 個の値を $f(P)$ に含めることができます。 $f(P)=X$ から、そこに含まれない値を特定することができます。

ヒント 4

$\min((P_i,P_{i+1},P_{i+2})\text{の中央値}\mid i=1,3,\dots,N-2)$ がある値（$p$ と置く）になるような $P$ を数え上げる問題になります。 この値が $p$ 以上になる $P$ の総数から $p+1$ 以上になる $P$ の総数を引けば答えを求めることができます。

ヒント 5

$\min((P_i,P_{i+1},P_{i+2})\text{の中央値}\mid i=1,3,\dots,N-2)$ が $p$ 以上になる $P$ の総数を考える場合、$p$ 未満の数同士と $p$ 以上の数同士は区別する必要が無いため、それぞれ $0,1$ に置き換えて考えることができます。

ヒント 6

$0,1$ に置き換えた数列に含まれる $0$ の個数は $p-1$ 個にする必要があります。 左の要素から $0,1$ のどちらを割り振るかを決めていくことにして、割り振った $0$ の個数をキーにして dp をしたいですが、普通にやると $O(N^2)$ かかってしまいます。 どうすれば高速化できるでしょうか？