A - Communicate Topological Order

ヒント 1

グラフに辺が $1$ 本もないとき、$N-1$ 個の項を伝えないと、青木君は $P$ を特定できません。

ヒント 2

$P_i$ が連続する頂点集合 $S$ に含まれる $2$ 頂点間に辺が無いとき、$S$ の頂点のうち $|S|-1$ 個の項は青木君に伝える必要があります。

ヒント 3

逆に言えば、$N$ 頂点をそのような頂点集合に分割したとき、各集合から $1$ 個の項は青木君に伝えなくてもいいことになります。 実は、最適に分割された頂点集合の頂点番号は連続としてよいことが証明できます。 ただし、そのような分割方法にはもう一つ制約があります。 それは何でしょうか？

ヒント 4

ヒント 3 の答えは、頂点集合ごとの順番が定まることです。 例えば、各頂点集合内の頂点の順番が決まったとしても、頂点集合同士が $G$ において独立していたら、青木君は $P$ を特定することができません。

ヒント 5

ヒント4の条件も満たすように、$N$ 頂点をできるだけたくさんの頂点集合に分割したいです。何をどのように計算していけばよいでしょうか？

B -Swap if Equal Length and Sum

ヒント 1

操作によって $A$ の総和は不変ですが、他にも不変量が存在します。

ヒント 2

操作によって転倒数も不変量です。 実は、$A$ と $B$ の総和と転倒数が等しいならば、必ず可能です。 具体的な操作手順を考えてみましょう。

ヒント 3

$1$ を $1$ 個含むような区間を入れ替える操作を $N$ 回行うことで $A$ を $B$ に一致させることができます。

ヒント 4

ヒント 3 の操作手順を元にして少し工夫することで、操作回数を $\lfloor\frac{N}{2}\rfloor$ 回以下に抑えることができます。

C - PORALIS

writer 解のヒント

ヒント 1

$N$ が $2$ べきのときを考えてみましょう。

ヒント 2

$P_i$ の (2進法における）下 10 bit を $i-1$ にすると、上 20 bitの最長広義単調増加列を考えればよいことになります。

ヒント 3

$P_i$ の上 20 bit のうち、$1$ である bit を高々 $1$ つ にしてみましょう。

ヒント 4

ヒント 2,3 を使って、できるだけ多くの LIS 長を達成してみましょう。

ヒント 5

$\displaystyle \frac{N}{2}$ のときの解を利用できないか考えてみましょう。

tester 解のヒント

ヒント 1

$N^3 = \max(P, A)$ であることから、使用する bit を $2,3$ 個増やして $N$ を $2$ 倍以上にできればよいです。

ヒント 2

ある $N$ で条件を達成する $(P, A)$ が構築できたとき、使うビットを 1 つ増やして $N+1$ で条件を達成してみましょう。

ヒント 3

ある $N$ で条件を達成する $(P, A)$ が構築できたとき、$(P_1, P_2, \dots, P_N, P_1 + 2^X, P_2 + 2^X, \dots, P_N + 2^X)$ に対して、$A_1, A_2, \dots, A_N$ のそれぞれを $\mathrm{OR}$ したときの LIS 長はどうなりますか？

ヒント 4

ヒント $3$ で偶数の LIS 長は簡単に達成できます。 使う bit を 1 つ増やしてすべての LIS 長も達成してみましょう。

D - Valid Output for DSU Problems

ヒント 1

辺を張るクエリの順番を固定したときに、得られる数列 $A$ の条件について考えてみましょう。

ヒント 2

連結である $2$ 頂点の組の個数が $A$ に含まれる $1$ の個数以上に初めてなるタイミングを考えてみましょう。

ヒント 3

辺を張るクエリの順番が決まっているとき、条件を満たすために必要な操作回数はどのように求められるでしょうか？

ヒント 4

辺を張るクエリの順番の固定を外します。操作回数を求めるためには何がわかればいいでしょうか？

ヒント 5

そのような並べ方が可能かを動的計画法で調べます。実行時間に間に合わせるためには何を求めていけばいいでしょうか？

E - Delete AB

ヒント 1

`A` を $+1$、`B` を $-1$ に置き換えて累積和を取ってみましょう。

ヒント 2-1

ヒント $1$ で考えた累積和に対して、以下の $3$ つを考えてみましょう。

• 操作によって、どのように変化しますか。
• 操作しても変わらないものはありますか。
• 回文であることは、累積和がどのような状態になることですか。

ヒント 2-2

• 操作によって、ある条件を満たす要素 $2$ つが削除されます。
• 最初の値、最後の値、最小値は変化しません。
• 累積和の前から $i$ 項目と後ろから $i$ 項目の和が、$i$ によらず常に同じであることが必要十分条件です。

ヒント 3

累積和の最小値は変化しないので、それに対応する要素が必要です。

ヒント 4

累積和の min と、それに対応する要素として残すものを 1 組固定します。その内側、外側についてそれぞれどのようにするのが最適でしょうか。

ヒント 5

ヒント 4 の外側について、prefix の min (あるいは suffix の min) は変わりません。

ヒント 6

累積和の min やそれに対応する要素が複数存在する場合、どれを残すのが最適でしょうか。