ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）E,F,G問題メモ

ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）

E - Snowflake Tree

• 「ユ木」を、以下の手順で生成することができる木と定義します（元の問題ページも参照）。
  1. 正整数 $x,y$ を選ぶ
  2. 頂点を $1$ つ用意する
  3. 別に $x$ 個の頂点を用意し、それぞれを手順 $2$ で用意した頂点と辺で結ぶ
  4. 手順 $3$ で用意した $x$ 個の頂点それぞれに、$y$ 個の葉をつける
• $N$ 頂点の木 $T$ が与えられます。頂点には $1$ から $N$ の番号が付けられており、 $i\;(=1,2,\dots,N-1)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。
• $T$ の $0$ 個以上の頂点とそれに隣接する辺を削除して $1$ つのユ木にするとき、削除する頂点数の最小値を求めてください。
• なお、本問題の制約下で、$T$ をかならずユ木にすることができます。

• $3 \leq N \leq 3 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• 与えられるグラフは木である
• 入力はすべて整数

どこかメルヘンチックな問題。

各頂点に付き、「この頂点を中心としたときに、最大何頂点のユ木が作れるか？」を求める。

例えば、頂点 $v$ に隣接する頂点の次数が大きい順に $9,7,6,6,3,1,1$ だったとして、

• $x=1$ とした場合、次数 $9$ の隣接頂点を採用して $y=8$ とし、$1+9 \times 1=10$ 頂点のユ木を作れる
• $x=2$ とした場合、次数 $9,7$ の隣接頂点を採用して $y=6$ とし、$1+7 \times 2=15$ 頂点のユ木を作れる
• $x=3$ とした場合、次数 $9,7,6$ の隣接頂点を採用して $y=5$ とし、$1+6 \times 3=19$ 頂点のユ木を作れる
• $x=4$ とした場合、次数 $9,7,6,6$ の隣接頂点を採用して $y=5$ とし、$1+6 \times 4=25$ 頂点のユ木を作れる
• …

$x=4,y=5$ の時に最大となる。

これを全頂点に対して調べ、$N-$（最大のユ木の頂点数）が答え。

全体を通して合計 $O(N)$ 要素のソートを行うので、計算量は $O(N \log{N})$

Python3

F - Visible Buildings

• $1$ から $N$ の番号がついた $N$ 棟のビルが数直線上に建っています。
• ビル $i$ は座標 $X_i$ にあり、高さは $H_i$ です。ビルの高さ方向以外の大きさは無視できるものとします。
• 座標 $x$ の高さ $h$ の地点 $P$ からビル $i$ が見えるとは、ビル $i$ 上のある点 $Q$ であって、線分 $PQ$ が他のビルと共有点を持たないものが存在することと定めます。
• 座標 $0$ から全てのビルを見ることができない高さの最大値を求めてください。
• ただし、高さは非負の値を取るとし、高さ $0$ で全てのビルを見ることができる場合はかわりに -1 と答えてください。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq X_1 \lt \dots \lt X_N \leq 10^9$
• $1 \leq H_i \leq 10^9$
• 入力は全て整数である

$N$ 点の $(X_i,H_i)$ から2点選んで、その2点を通る直線の切片（$x=0$ の時の $y$ 座標）の最大値を求めればよい。

当然、愚直にやると $O(N^2)$ でダメ。
性質を見極め、不要なペアは調べないようにする。

実は、隣接2点以外は調べなくてよい。
∵ 3点 $i \lt j \lt k$ を取ると、$(i,k)$ を通る直線の切片は必ず、 $(i,j)$、$(j,k)$ を通る直線の切片のいずれか以下となる。

• 公式Editorial

答えは誤差が許されていそうで、$0.0$ と $-0.000...001$ を明確に区別しないといけないため、実は許されない。

Pythonなら、Fractionを使えば有理数を（分子・分母）の整数値の組でもって計算してくれるので、正確な値が求まる。
安易に使うと、分数同士の演算が重なった時に分母が爆発するのでTLEするが、 今回はせいぜい分子・分母の絶対値 $\le 10^9$ で傾きを求めた後は、整数との演算か、同精度の分数との比較しか行われないので大丈夫。

もし小数で比較する場合は、個々の切片を求める際、式変形して整数で処理できる部分をなるべく先に計算し、割り算を最後に1回だけ行うようにした方が、誤差が発生しにくい。
なんと、この問題ではそれをするかどうかがACかWAの分水嶺の1つとなるくらい絶妙な制約だったらしい。

• rsk0315氏によるユーザー解説

隣接頂点以外を調べなくてよいことに気付かなかった解法

G - Counting Buildings

• $(1,2,\dots,N)$ の並び替え $P=(P_1,P_2,\dots,P_N)$ に対し、整数 $L(P),R(P)$ を以下のように定めます。
  • $N$ 個のビルが左右一列に並んでおり、左から $i$ 番目のビルの高さは $P_i$ であるとする。
  • このビルの列を左側から見たときに見えるビルの数を $L(P)$、右側から見たときに見えるビルの数を $R(P)$ とする。
  • より形式的には、$L(P)$ はすべての $j \lt i$ に対して $P_j \lt P_i$ を満たす $i$ の個数であり、$R(P)$ はすべての $j \gt i$ に対して $P_i \gt P_j$ を満たす $i$ の個数である。

• 整数 $N,K$ が与えられます。$(1,2,\dots,N)$ の並び替え $P$ であって、$L(P)-R(P)=K$ となるようなものの個数を $998244353$ で割ったあまりを求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $|K| \leq N-1$
• 入力はすべて整数

挿入DPと畳み込み。

$P_i$ の大きい方から、ビルの高さ列 $P$ を構築していくことを考える。

既に大きい方から $i$ 個の要素の順番を決めているとき、$i+1$ 個目の要素をどこに挿入するかを考える。

N=9  i=5  4を挿入する場所を考える

  8   9   6   7   5
^   ^   ^   ^   ^   ^

挿入前の時点では、暫定で $L(P)=2,R(P)=3$ となっている。
4を左端に挿入すると $L(P)=3$ となる。右端に挿入すると $R(P)=4$ となる。その他の位置では変化しない。
以下のDPで計算できそうである。

• $\mathrm{DP_仮}[i,j,k]:=$ 大きい方から $i$ 個までの順番を決め、暫定 $L(P)=j,R(P)=k$ となる数列の個数

ただ、これだと状態数が $O(N^3)$ となり余裕のTLEとなる。

よく考えると、$L(P)-R(P)$ が同じものは遷移が同じなのでまとめて計算できる。

• $\mathrm{DP}[i,j]:=$ 大きい方から $i$ 個までの順番を決め、暫定 $L(P)-R(P)=j$ となる数列の個数

左端に挿入すると $j+1$、右端に挿入すると $j-1$ に遷移する。
それ以外の $i-1$ 箇所への挿入では変化せず $j$ に遷移する。

■DP遷移
              j
DP[i]        ○
           ↙↓↘
DP[i+1]  x1 xi-1 x1

愚直な遷移だとまだ $O(N^2)$ だが、 この遷移は $j$ に依らないので、同じ $i$ からの遷移は全て同じになる。

DP[i]        ... ○ ○ ○ ○ ○ ○ ○ ...

          ... ○ ○ ○ ○ ○ ○ ○ ...       x1
        +    ... ○ ○ ○ ○ ○ ○ ○ ...    xi-1
        +       ... ○ ○ ○ ○ ○ ○ ○ ... x1
       --------------------------------------
DP[i+1]   ... ○ ○ ○ ○ ○ ○ ○ ○ ○ ...

形式的冪級数で表せ、$(x^{-1}+0+x)(x^{-1}+1+x)(x^{-1}+2+x)...(x^{-1}+N-2+x)$ の $x^K$ の係数が答えとなる。

マージテクで小さい方から畳み込んでいくと、$O(N (\log{N})^2)$ で求められる。

Python3