Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）E,F問題メモ

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）

ぎゃーす。だめでした。

E - Make it Palindrome

• ある数列 $X$ に対し、$f(X)$ を「その数列を回文にするために変更する必要のある要素の個数」とする
• 長さ $N$ の数列 $A$ が与えられる
• $A$ の全ての連続部分列 $X$ について $f(X)$ を計算し、その総和を求めよ
• $1 \le N \le 2 \times 10^5$

基本的には公式解説の通り。

• 同じ要素が1つもない最大ケースを考えて、そこから変更しなくてすむ回数を除く
• 変更しなくて済む回数は、主客転倒を用いて数える
  • つまり変更しなくてよいペア毎に、それが何通りの $X$ に出現するか考える

$X$ が決まっているとき、$f(X)$ は「左右端からの距離が同じ要素同士をペアとして、異なっているペアの個数」となる。

X:  1 2 3 4--4 3 2 1
    | | `------' | |
    | `----------' |
    `--------------'

$X$ が $A$ の連続部分列であることを踏まえたとき、ある2要素 $(i,j)$（$i \lt j$）がペアとなるような連続部分列 $X$ は何個か？

これは、$\min(i$ が左から何番目か, $j$ が右から何番目か$)$ 個となる。
一番短いケース（＝$i,j$ がそれぞれ左右端の場合）から、ペアを保ったまま別の $X$ とするには、両端に1つずつ広げていくしかないので、その広げられる回数となる。

3と6がペアとなるようなX

A:  1  2  3  4  5  6  7  8  9
          ~        ~
          |--------|
       |--------------|
    |--------------------|

各要素について個別に考えやすくするため、ペアの数自体より「各要素がペアの片割れとなる回数」の合計値で考える。これはペア数の2倍となる。

$i$ を0-indexedとする。

$i$ が含まれるような区間 $l \le i \le r$ を決めれば、何かしら $i$ とペアになるものは1つ決まる。
$l$ の決め方が $i+1$、$r$ が $n-i$ で、$(i+1)(n-i)$ 回となる。

そのうち、$i$ がちょうど中央で $i$ 自身とペアになってしまう場合は、変更不要のため、今回は除いて考えたい。
そのようなものは $\min(i+1,n-i)$ 個ある。

よって、$(i+1)(n-i)-\min(i+1,n-i)$ を $i=0～N-1$ について合計したものの半分が最大ケースとなる。

除けるのは、同じ要素同士がペアになる回数となる。

i:  0  1  2  3  4
A:  2  1  4  1  1     → 1の出現位置は 1,3,4
                         (1,3) がペアになるXが2通り、
                         (1,4)が1通り、(3,4)が1通り
                      → 4回、変更しなくて済む（最大ケースから除ける）

ある要素を固定して、その出現位置を列挙したものを $P=(i_0,i_1,...)$ とする。

$P$ から2つ選んでペアとし、それが何個の $X$ で数えられるかを求めたいが、 しかしペアの数は最大 $O(N^2)$ となるため、1つ1つ考えることはできない。

「左または右にある要素数が少ない $i$ の順」にペアの一方を固定すると、上手くまとめられる。

たとえば $P=(0,2,5,9,11,15)$ の場合、次のような表を埋めることを考えると、

N=20
 L \ R i  0  2  5  9 11 15
 i  \    20 18 15 11  9  5    ←右から何番目か
 -------------------------
 0  1     -  1  1  1  1  1    ← 左をL,右をR としたペアが何回数えられるか
 2  3        -  3  3  3  3      = min(Lが左から何番目か, Rが右から何番目か)
 5  6           -  6  6  5
 9 10              -  9  5
11 12                 -  5
15 16                    -
   ↑左から何番目か

こんな風になる。
行(L)は上から、列(R)は右から、値を比較し、小さい方がその行/列のうち埋まっていない部分を総取りして次の行/列へ、ということを繰り返すようなイメージ。

最初の比較で総取りできるのは、(同じ要素の出現数-1) 個で、そこから1回毎に1つずつ減っていく。
こうすれば効率的に、除ける回数を計算できる。

Python3

F - Maximum Diameter

• 長さ $N$ の正整数列 $X=(X_1,...,X_N)$ が以下の条件を満たすとき、$X$ を「良い数列」とよぶ
  • $N$ 頂点の木で、頂点 $i$ の次数がちょうど $X_i$ であるようなものが存在する
• 良い数列に対し、$f(X)$ を以下で定義する
  • 上記の条件を満たして生成できる木のうち、直径が最大であるものの直径（たどる辺数）
• 全ての良い数列に対し、$f(X)$ の総和を求めよ
• 1つの入力につき $T$ ケース与えられる
• $1 \le T \le 2 \times 10^5$
• $2 \le N \le 10^6$

Eに続き、また主客転倒の考え方を用いる。

すぐわかることとして、

• 木なので辺数は $N-1$ 本。次数は両端で数えられることを踏まえると $X$ の総和は $2N-2$
• 連結でないといけないので、$X_i \ge 1$（そもそも問題が“正整数列”となっているので不要だが、一応）

逆にこれを満たせば、何なりと作ることはできる。
また、その時の直径の最大値は、「$X_i \ge 2$ である要素数+1」である。

作り方を示す。直径はパスなので、両端は $X_i=1$ であり、それ以外の次数は2以上ないといけない。 次数2以上の頂点をあるだけ繋げてやる。もしその上で木が作れるなら、これが可能な直径の最大値である。

   1--3--2--2--5--2--4--1
      |       /|\    /\
      o      o o o  o  o

2以上の頂点を全て使ったら、残っているのはあぶれた“1”のみであり、その個数は直径上にある2以上の $X_i$ の、余っている次数と一致する。よってそれを結んでやればよい。

2以上となる要素数 $k$ を固定すると、

• その選び方 ${}_N C_{k} \times$ 割り振り方 ${}_k H_{N-2} \times$ 直径 $(k+1)$

この $k=1～N-2$ の合計となる、、、が、今回は複数ケースに対して出力が求められるため、$O(TN)$ となり無理。
$N$ が1つ小さいケースからの差分などに良い性質があればよいが、見つからず。

以下を求めたい。

• 各 $X$ につき、(2以上となる $X_i$ の個数+1) の総和

主客転倒し、

• ＝($X$ の個数) + ($\displaystyle \sum_{i} X_i$ が2以上となるような $X$ の個数)

といえる。さらに対称性より、

• ＝($X$ の個数) + ($X_1$ が2以上となるような $X$ の個数 $\times N$)

$X$ の個数は、$X_i$ に1ずつ配った後、総和 $2N-2$ の残りの $N-2$ を $N$ 個に配る重複組み合わせなので、${}_N H_{N-2}$

$X_1$ が2以上となるのは、上記で $X_1$ にあらかじめ配る数を2にすればよいので、${}_N H_{N-3}$

これで、階乗の事前計算により、各 $N$ につき $O(1)$ で求められるようになる。

この対称性を利用したまとめ方、いっつも忘れてるな･･････

Python3