ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)F,G問題メモ

ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)

F - Cans and Openers

• $N$ 個の品物があり、これらは「缶切り不要の缶」「缶切り必要な缶」「缶切り」のいずれか
• 品物は $(T_i,X_i)$ の2つの整数の組により、以下のように表される
  • $T_i=0$: 缶切り不要な缶、開けると満足度 $X_i$
  • $T_i=1$: 缶切り必要な缶、缶切りを使って開けると満足度 $X_i$
  • $T_i=2$: 缶切り、$X_i$ 個までの缶に対して使用できる
• $N$ 個中からあわせて $M$ 個を入手するとき、得られる満足度の合計の最大値をもとめよ
• $1 \le M \le N \le 2 \times 10^5$
• $1 \le X_i \le 10^9$

表記の簡素化のため、缶切り不要な缶を「不要缶」、必要な缶を「必要缶」とする。

缶切りも1つの品物で、3種類の品物があるところが厄介。

選ぶ品物の種類1つの個数を固定して、残りを差分更新などで $O(1)$ などで求められればよい。

「同じ品物同士」の中からは、単純に $X_i$ の大きい方から選んだ方が得。

まず、缶切り0個の場合、不要缶のみを $X_i$ の大きい方から最大 $M$ 個、選べる。

缶切りを1つ追加（$X$ 個まで開けれる）すると、缶は合計 $M-1$ 個と選べる数が1減るが、 必要缶を追加で $X$ 個まで｛新たに選ぶ or 不要缶と入れ替える｝ことができる。

よって、

• 選んでる缶を、$X_i$ の小さい方から取り出せる優先度付きキュー $S$
• 選んでない必要缶を大きい方から取り出せるスタック $T$

を用意して、缶切りを1つ増やすたびに

1. $|S|$ が選べる缶の個数をオーバーしてたら1つ減らし、捨てる
2. $|S|$ が足りなければ、$T$ から必要缶を「選べる缶の合計個数」も「必要缶を開けられる個数」もオーバーしない範囲で増やせる
3. $|S|$ ＝選べる缶の合計個数となったら、「必要缶を開けられる個数」をオーバーしない範囲で、$S$ と $T$ の先頭を見て、$S.top < T.top$ なら入れ替えられる

として、差分を更新していくとよい。

1.に関して、缶切りを増やし続ける限り「選べる缶の合計個数」は減り続けるし「選べる必要缶の個数」は増え続ける。
popした缶は、不要缶でも必要缶でも、もうそれは選ばれることは無い。
特に、$T.top$ がpopした缶以下だった場合は、後から追加できる缶でもう改善することはないため、打ち切っても良い

2.に関して、足りないということは、不要缶は既に全て選ばれているので、そちらから選ぶことは考慮しなくてよい。

3.に関して、$T$ は大きい方から追加していっているので $S$ に入っている不要缶は、必ず $T$ 以上。
よって $S.top < T.top$ の場合、$S.top$ は必ず不要缶。

などの枝刈りにより若干実装は簡潔にできるが、このあたりを考察するよりは実装した方が速い or 確実という場合もある。

Python3

G - Avoid Straight Line

• $N$ 頂点の木が与えられる
• 3頂点 $i,j,k$ の組で、3点が全て含まれる単純パスが存在しないようなものの個数を求めよ
• $1 \le N \le 2 \times 10^5$

「単純パスが存在しない」ということは、「3頂点は、それとは別のある1頂点から出る別々の3辺の先にある」ことと同じである。

ⓘ←○←◎→○→ⓙ→○
        ↓       `→○
        ○→ⓚ

2頂点 $i,j$ を固定すると、$i,j$ を結ぶ単純パス上の点、および「$i$ の、$j$ から遠ざかる側の部分木」やその逆の点は、 $k$ として選ばれると一直線になってしまう。

それに該当しないのは、「$i,j$ を結ぶ単純パス上（両端除く）から分岐して他の枝に入る点」となる。

逆にそのような $i,j,k$ に対し、中央の点（◎）は必ず1点に決まる。（前述の“分岐点”がそれとなる）

よって、次数 $d \ge 3$ の頂点について、各部分木の先にある頂点数 $w_1,w_2,...,w_d$ から3つを選んで掛け合わせればよい。

全ての3つ組の積の総和が、その頂点を中央とする $i,j,k$ の選び方となる。

で、3つ組の積の総和をどうやって求めるかだが、以下の式変形が利用できる。

• $(a+b+c+d)^3=(a^3+b^3+c^3+d^3)+(3a^2(b+c+d)+3b^2(a+c+d)+3c^2+(a+b+d)+3d^2(a+b+c))+6(abc+abd+acd+bcd)$

総和の3乗から、3乗の和や2乗の和を引いたりすると、「別々の3つ」を選んだ合計が残る。

具体的には、$w_1,w_2,...$ の総和を $W_1$、2乗の和を $W_2$、3乗の和を $W_3$ とすると、

• $\dfrac{W_1^3-3W_1W_2+2W_3}{6}$

となる。適当な頂点を根とした、各頂点の部分木の頂点数を数える木DPで求められる。

Python3